Algorithm

E. Squares and not squares
time limit per test
2 seconds
memory limit per test
256 megabytes
Problem link- https://codeforces.com/contest/898/problem/E
input
standard input
output
standard output

Ann and Borya have n piles with candies and n is even number. There are ai candies in pile with number i.

Ann likes numbers which are square of some integer and Borya doesn't like numbers which are square of any integer. During one move guys can select some pile with candies and add one candy to it (this candy is new and doesn't belong to any other pile) or remove one candy (if there is at least one candy in this pile).

Find out minimal number of moves that is required to make exactly n / 2 piles contain number of candies that is a square of some integer and exactly n / 2 piles contain number of candies that is not a square of any integer.

Input

First line contains one even integer n (2 ≤ n ≤ 200 000) — number of piles with candies.

Second line contains sequence of integers a1, a2, ..., an (0 ≤ ai ≤ 109) — amounts of candies in each pile.

Output

Output minimal number of steps required to make exactly n / 2 piles contain number of candies that is a square of some integer and exactly n / 2 piles contain number of candies that is not a square of any integer. If condition is already satisfied output 0.

Examples
input
Copy
4
12 14 30 4
output
Copy
2
input
Copy
6
0 0 0 0 0 0
output
Copy
6
input
Copy
6
120 110 23 34 25 45
output
Copy
3
input
Copy
10
121 56 78 81 45 100 1 0 54 78
output
Copy
0
Note

In first example you can satisfy condition in two moves. During each move you should add one candy to second pile. After it size of second pile becomes 16. After that Borya and Ann will have two piles with number of candies which is a square of integer (second and fourth pile) and two piles with number of candies which is not a square of any integer (first and third pile).

In second example you should add two candies to any three piles.

 



 

Code Examples

#1 Code Example with C++ Programming

Code - C++ Programming

#include <bits/stdc++.h>

typedef long long ll;

using namespace std;

long long const N = 3e5 + 1;
long long n, a[N], mn[N], sqrs[32001], cnt = 0;
bool vis[N];

int main() {
	for(int i = 0; i < 32001; ++i)
		sqrs[i] = i * i;

	scanf("%lld", &n);
	for(int i = 0; i < n; ++i) {
		scanf("%lld", a + i);
		if(binary_search(sqrs, sqrs + 32001, a[i])) {
			vis[i] = true;
			++cnt;
		}
	}

	if(cnt == n / 2) {
		puts("0");
		return 0;
	}

	for(int i = 0, idx; i < n; ++i) {
		idx = lower_bound(sqrs, sqrs + 32001, a[i]) - sqrs;
		if(idx < 32001 && sqrs[idx] == a[i])
			mn[i] = 0;
		else {
			long long after = 2e16, before = 2e16;
			if(idx < 32001)
				after = abs(sqrs[idx] - a[i]);

			if(idx - 1 >= 0)
				before = abs(a[i] - sqrs[idx - 1]);

			mn[i] = min(after, before);
		}
	}

	long long sol = 0;

	if(cnt > n / 2) {
		cnt -= (n / 2);
		for(int i = 0; cnt > 0 && i < n; ++i) {
			if(vis[i] && a[i] != 0) {
				++sol;
				--cnt;
			}
		}

		for(int i = 0; cnt > 0 && i < n; ++i) {
			if(vis[i] && a[i] == 0) {
				sol += 2;
				--cnt;
			}
		}

		printf("%lld\n", sol);
		return 0;
	}

	sort(mn, mn + n);

	for(int i = 0; i < n / 2; ++i)
		sol += mn[i];

	printf("%lld\n", sol);

	return 0;
}
Copy The Code & Try With Live Editor

Input

x
–
+
cmd
4
12 14 30 4

Output

x
–
+
cmd
2
Advertisements

Demonstration

Codeforces Solution-Squares and not squares-Solution in C, C++, Java, Python

Previous
Codeforces solution 1080-B-B. Margarite and the best present codeforces solution
Next
CodeChef solution DETSCORE - Determine the Score CodeChef solution C,C+