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

Задача A. Крутой подарок

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

1 секунда

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

256 мегабайт

У Темирлана недавно был день рождения. Из его друзей самый оригинальный подарок решил сделать его друг, Айсултан. Айсултан знает, что Темирлан любит крутые числа. Число называется крутым, если оно является квадратом целого числа. Например, $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;
}

C++

Copy

показать/скрыть код

C++

Copy

#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;

}

показать/скрыть код

C++

Copy

#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);

}

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

показать/скрыть код

C++

Copy

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;
}

C++

Copy

показать/скрыть код

#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;
}

C++

Copy