codeforces-scrape

Codeforces scraped problems and editorials
git clone git://git.laack.co/codeforces-scrape.git
Log | Files | Refs | README

898E.md (2103B)


      1 Source: https://codeforces.com/problemset/problem/898/E
      2 
      3 E. Squares and not squares
      4 
      5 time limit per test
      6 
      7 2 seconds
      8 
      9 memory limit per test
     10 
     11 256 megabytes
     12 
     13 input
     14 
     15 standard input
     16 
     17 output
     18 
     19 standard output
     20 
     21 Ann and Borya have *n* piles with candies and *n* is even number. There are *a**i* candies in pile with number *i*.
     22 
     23 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).
     24 
     25 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.
     26 
     27 Input
     28 
     29 First line contains one even integer *n* (2 ≤ *n* ≤ 200 000) — number of piles with candies.
     30 
     31 Second line contains sequence of integers *a*1, *a*2, ..., *a**n* (0 ≤ *a**i* ≤ 109) — amounts of candies in each pile.
     32 
     33 Output
     34 
     35 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.
     36 
     37 Examples
     38 
     39 Input
     40 
     41 ```
     42 4  
     43 12 14 30 4
     44 ```
     45 
     46 Output
     47 
     48 ```
     49 2
     50 ```
     51 
     52 Input
     53 
     54 ```
     55 6  
     56 0 0 0 0 0 0
     57 ```
     58 
     59 Output
     60 
     61 ```
     62 6
     63 ```
     64 
     65 Input
     66 
     67 ```
     68 6  
     69 120 110 23 34 25 45
     70 ```
     71 
     72 Output
     73 
     74 ```
     75 3
     76 ```
     77 
     78 Input
     79 
     80 ```
     81 10  
     82 121 56 78 81 45 100 1 0 54 78
     83 ```
     84 
     85 Output
     86 
     87 ```
     88 0
     89 ```
     90 
     91 Note
     92 
     93 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).
     94 
     95 In second example you should add two candies to any three piles.