codeforces-scrape

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

962C.md (1527B)


      1 Source: https://codeforces.com/problemset/problem/962/C
      2 
      3 C. Make a Square
      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 You are given a positive integer $n$, written without leading zeroes (for example, the number 04 is incorrect).
     22 
     23 In one operation you can delete any digit of the given integer so that the result remains a positive integer without leading zeros.
     24 
     25 Determine the minimum number of operations that you need to consistently apply to the given integer $n$ to make from it the square of some positive integer or report that it is impossible.
     26 
     27 An integer $x$ is the square of some positive integer if and only if $x=y^2$ for some positive integer $y$.
     28 
     29 Input
     30 
     31 The first line contains a single integer $n$ ($1 \le n \le 2 \cdot 10^{9}$). The number is given without leading zeroes.
     32 
     33 Output
     34 
     35 If it is impossible to make the square of some positive integer from $n$, print -1. In the other case, print the minimal number of operations required to do it.
     36 
     37 Examples
     38 
     39 Input
     40 
     41 ```
     42 8314
     43 ```
     44 
     45 Output
     46 
     47 ```
     48 2
     49 ```
     50 
     51 Input
     52 
     53 ```
     54 625
     55 ```
     56 
     57 Output
     58 
     59 ```
     60 0
     61 ```
     62 
     63 Input
     64 
     65 ```
     66 333
     67 ```
     68 
     69 Output
     70 
     71 ```
     72 -1
     73 ```
     74 
     75 Note
     76 
     77 In the first example we should delete from $8314$ the digits $3$ and $4$. After that $8314$ become equals to $81$, which is the square of the integer $9$.
     78 
     79 In the second example the given $625$ is the square of the integer $25$, so you should not delete anything.
     80 
     81 In the third example it is impossible to make the square from $333$, so the answer is -1.