Đống kẹo chính phương

Điểm: 5,00 (OI)

Giới hạn thời gian: 2.0s

Giới hạn bộ nhớ: 256M

Đầu vào: stdin

Đầu ra: stdout

Dạng bài

Ngôn ngữ cho phép

Ada, Algol, Assembly, Awk, C, C#, C++, D, Dart, Forth, Fortran, Go, Groovy, Java, Javascript, Kotlin, Lisp, Lua, Nim, ObjC, Pascal, Perl, PHP, Pike, Python, Racket, Ruby, Rust, Scheme, Scratch, Sed, TCL, Typescript, V, Zig

Cho $n$ đống kẹo (với $n$ chẵn). Đống thứ $i$ chứa $a_{i}$ viên kẹo.

Trong một bước, bạn được chọn một đống bất kỳ rồi thêm một viên kẹo mới vào đống đó, hoặc bớt đi một viên (chỉ khi đống đang có ít nhất một viên).

Hãy tìm số bước ít nhất để sau khi thực hiện, có đúng $n / 2$ đống mà số kẹo trong đống là số chính phương, và đúng $n / 2$ đống còn lại có số kẹo không phải số chính phương.

Lưu ý: Số $0$ là số chính phương (vì $0 = 0^{2}$ ).

Dữ liệu vào

Dòng thứ nhất chứa số nguyên chẵn $n$ .
Dòng thứ hai chứa $n$ số nguyên $a_{1}, a_{2}, \dots, a_{n}$ .

Dữ liệu ra

In ra một số nguyên duy nhất — số bước ít nhất cần thực hiện. Nếu trạng thái ban đầu đã thỏa mãn yêu cầu, in ra $0$ .

Ràng buộc

$2 \leq n \leq 2 \cdot 10^{5}$ và $n$ chẵn.
$0 \leq a_{i} \leq 10^{9}$ .

Ví dụ

Input	Output	Giải thích
4 12 14 30 4	2	Thêm $2$ viên vào đống thứ hai để $14 \to 16 = 4^{2}$ . Khi đó các đống chính phương là đống $2$ và đống $4$ (cùng $= 4$ ), hai đống còn lại không phải chính phương.
6 0 0 0 0 0 0	6	Cả $6$ đống đều bằng $0$ — đều là số chính phương. Để có $3$ đống không phải chính phương, ta thêm $2$ viên vào ba đống bất kỳ (mỗi đống $0 \to 2$ ), tổng $6$ bước.
6 120 110 23 34 25 45	3	$25 = 5^{2}$ là đống chính phương duy nhất. Đưa $120 \to 121 = 11^{2}$ (mất $1$ ) và $34 \to 36 = 6^{2}$ (mất $2$ ) cho ta thêm $2$ đống chính phương, tổng $3$ bước.
10 121 56 78 81 45 100 1 0 54 78	0	Đã có $5$ đống chính phương ( $121, 81, 100, 1, 0$ ) và $5$ đống không phải chính phương.

Bình luận

Không có bình luận tại thời điểm này.