Районная олимпиада по информатике. 2018-2019 учебный год. 8-11 классы

Есеп A. Керемет сыйлық

Ограничение по времени:

1 second

Ограничение по памяти:

256 megabytes

Жақында Темірланның туған күні болды. Ең қызық сыйлықты оның досы Айсұлтан жасады. Айсұлтан Темірланның керемет сандарды ұнататынын біледі. Айсұлтанның ойынша, белгілі бір сан кез келген басқа бір бүтін санның квадратына тең болса, ол сан керемет сан деп есептелінеді. Мысалы, $0$, $9$, $121$ — керемет сандар, ал $50$, $3$, $12$ — керемет сандар емес. Айсұлтанда қазір $n$ бүтін саннан тұратын массив бар — $a_1, a_2, a_3, ..., a_n$. Сыйлық жасау үшін, осы тізбектен Айсұлтан екі сан $a_j$ и $a_i$ ($j < i$) алып, олардың көбейтіндісінің керемет сан бола алуын тексереді. Егер де, көбейтінді сан $a_j * a_i$ керемет болса, онда Айсұлтан көбейтіндіні Темірланға сыйлай алады деген сөз. Айсұлтан сыйлықты неше түрлі жолмен жасай алатынын анықтаңыз. Басқаша айтқанда, тізбектен $(a_j, a_i)$ жұптарының арасында $j < i$ болатын және $a_j * a_i$ көбейтіндісі керемет сан болатын жұптардың санын табыңыз.

Формат входного файла

Бірінші жолда тек $n$ берілген — тізбектің ұзындығы $(1 \le n \le 10^3)$. Екінші жолда бос орын арқылы жазылған $n$ бүтін саннан тұратын тізбек $a_1, a_2, a_3, ..., a_n$ берілген — Айсұлтанның тізбегі $(-1000 \le a_i \le 1000)$.

Формат выходного файла

Тек бір сан, яғни, Айсұлтанның неше жолмен сыйлық жасай алатынын шығаруыңыз керек.

Примеры:

Вход

4
1 0 1 1

Ответ

6

Вход

2
-8 -2

Ответ

1

Вход

3
1 16 4

Ответ

3

Вход

1
0

Ответ

0

Замечание

Бұл есеп 3 бөлімнен тұрады:

1. $0 \le a_i \le 1$ барлық $1 \le i \le n$ үшін.
2. $n = 2$, $-1000 \le a_i \le 1000$.
3. Есептің берілгеніндегі шарттар.

Бірінші мысалда 6 жұптың барлығының көбейтіндісі 0 немесе 1 санының квадраты болып табылады. Екінші мысалда тек бір жұптың көбейтіндісі ережеге сәйкес — бүтін санның квадраты болатын 16 саны. Үшінші мысалда (1, 16), (1, 4), (16, 4) жұптарының барлығының көбейтіндісі бүтін санның квадраты болып табылады. Төртінші мысалда сыйлық құрай алатын бір де бір жұп жоқ. ( Almat Kenen )

Комментарий/решение

чтобы решить эту задачу, просто найти сколькими способами из n числов можно создать пар

значить просто возпользуемся формулам математики n!/(2*(n-2))

кодты корсету/жасыру

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios_base::sync_with_stdio(0); cin.tie(0);
    int n;
    cin >> n;
    int a[n];
    for (int i=0; i<n; i++) cin >> a[i];
    int ans=0;
    for (int i=0; i<n; i++) {
        for (int j=i+1; j<n; j++) {
            if (a[i]*a[j]>=0 && (double) sqrt(a[i]*a[j]) == (int) sqrt(a[i]*a[j])) ans++;
        }
    }
    cout << ans << '\n';
    return 0;
}

кодты корсету/жасыру

#include <bits/stdc++.h>

using namespace std;

int n, num[10005];//size, array

int k;//create counter

int main() {

cin >> n;

for (int i = 1; i <= n; i++){

cin >> num[i];

}

for (int i = 1; i <= n; i++) {

for (int j = i + 1; j <= n; j++) {

//check number

if ( num[i]*num[j] >= 0)

if((double) sqrt(num[i]*num[j]) == (int) sqrt(num[i]*num[j])){

k++;//update counter

}

}

}

cout << k;//answer

return 0;

}

кодты корсету/жасыру

#include <bits/stdc++.h>

using namespace std;

int main()

{

int n,a,counter=0;cin>>n;int mas[2001]={0};float san;

for(int i=0;i<n;i++)

{

scanf("%d",&a);mas[a+1000]++;

}

for(int i=0;i<=2000;i++)

{ if(mas[i]==0)continue;

counter+=(mas[i]-1)*(mas[i])/2;

for(int q=i+1;q<=2001;q++)

{

if(mas[q]==0)continue;

san=sqrt((i-1000)*(q-1000));

if(san==floor(san)&&san==ceil(san)){counter+=mas[i]*mas[q];}

}

}

printf("%d",counter);

}

решение через некий перебор

кодты корсету/жасыру

n = int(input())

arr = list(map(int, input().split()))

cntr = 0

for i in range(n):

for j in range(i+1, n):

if (arr[i] * arr[j])**0.5 % 1 == 0:

cntr += 1

print(cntr)

DELETED

кодты корсету/жасыру

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define max3(a, b, c) max(a, max(b, c))
#define min3(a, b, c) min(a, min(b, c))
#define mp make_pair
#define pb push_back
#define ub upper_bound
#define lb lower_bound
#define F first
#define S second
#define start ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define y1 asdasd
#define go continue

using namespace std;
using namespace __gnu_pbds;

typedef long long ll;
typedef unsigned long long ull;
typedef pair <int, int> pii;
typedef pair <ll, ll> pll;
typedef vector < int > vi;
typedef vector < pii > vii;
typedef vector < ll > vl;
typedef vector < pll > vll;
typedef set < int > si;
const int N = 1e5 + 123;
const int N2 = 1e6 + 123;
const int MOD = 1e9 + 7;
const int INF = 0x3f3f3f3f;
const ll VERYINF = 1e18 + 5;
const double pi = 3.141592653589;

int n, a[N], ans;

void input() {
	cin >> n;
	for(int i = 1; i <= n; i++) {
		cin >> a[i];
	}
}

bool check(int x, int y) {
	int c = x * y;
	int d = (int)sqrt(c);
	if(d * d == c)
		return true;
	return false;
}

void solve() {
	input();
	for(int i = 1; i <= n; i++)
		for(int j = i + 1; j <= n; j++)
			if(check(a[i], a[j]))
				ans++;
	cout << ans;
}

int main () {
	start
	solve();
	return 0;
}

кодты корсету/жасыру

#include <bits/stdc++.h>
using namespace std;

int main() {
  int n, count = 0;
  cin >> n;
  int arr[n];
  for(int i = 0; i < n; i++){
    cin >> arr[i];
  }
  for(int i = 0; i < n; i++){
    for(int j = i + 1; j < n; j++){
        int g=sqrt(arr[i]*arr[j]);
				if(g*g==arr[i]*arr[j]){
					count++;
				}
    }
  }
  cout << count;
}