codeforces 962 C. Make a Square

Description

You are given a positive integer n , written without leading zeroes (for example, the number 04 is incorrect).

In one operation you can delete any digit of the given integer so that the result remains a positive integer without leading zeros.

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.

An integer x is the square of some positive integer if and only if x = y2 for some positive integer y .

Input

The first line contains a single integer n ( 1≤n≤2⋅10 9 ). The number is given without leading zeroes.

Output

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.

Examples

Input
8314
Output
2

Input
625
Output

Input
333
Output
-1

Note

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 .

In the second example the given 625 is the square of the integer 25 , so you should not delete anything.

In the third example it is impossible to make the square from 333 , so the answer is −1 .

參考了下面的部落格

https://www.cnblogs.com/a249189046/p/8821300.html

題意：給一個整數，每次删除一個位，要求删除後的首位不能是0，問多少次操作以後變為平方數。

思路：百度了一下開方函數的複雜度，沒有看的很懂但是其中有一個說法是：

• 取對數->乘0.5->取指數

其中第一步和第三步可以用硬體實作，這樣下來複雜度就是O(1)的，是以用開方函數來檢查一個整數是否是平方數是可以的。

由于輸入最多有10位，搜尋起來最壞的情況要做10!次，這是不能接受的，這是由于重複搜尋導緻的，是以使用set記錄搜尋過的數字，把次數降到了2^10次（巨大的優化）

#include<stdio.h>
#include<math.h>
#include<queue>
#include<set>
using std::queue;
using std::set;
#define max(a,b) ((a)>(b)?(a):(b))
#define min(a,b) ((a)<(b)?(a):(b))
#define mabs(x) ((x)>0?(x):(0-(x)))
#define N_max 44722
int n;
int a10[N_max];
queue<int> a;
set<int> b;
int r(int x, int i) { 
    return x / a10[i + ]*a10[i] + x%a10[i]; 
}

int bfs(int len) {
    int next,temp;
    for (int k = ; k < len; ++k) {
        int t = a.size(), x;
        for (int i = ; i < t; ++i) {
            //周遊上一層産生的數
            x = a.front(); a.pop();
            for (int q = ; q < len - k; ++q) {//搜尋去掉每一位後産生的數
                if (q>&&q ==len-k- && ((x%a10[q]) / a10[q - ]) == )
                //判斷是否在首位以及同時第二位是否是0
                    continue;
                next = r(x, q);//生成下一個數
                if (next <= )continue;//特判
                //利用set檢查該數是否出現過
                if (b.find(next) == b.end())b.insert(next);
                else { continue; }
                //利用sqrt檢查該數是否是平方數
                temp = sqrt(next);
                if (temp*temp == next)
                    return k;
                //入隊列，為下一層bfs做準備
                a.push(next);
            }
        }
    }
}
int main() {
    scanf("%d", &n);

    int len = ,temp;
    temp = sqrt(n);
    if (temp*temp == n) {
        printf("0"); return ;
    }
    //計算位數，儲存在len裡
    for (temp = n; temp > ; ++len)temp /= ;
    //計算10, 100, 1000,...友善取模
    a10[] = ;
    for (int i = ; i < ; ++i) {
        a10[i] = a10[i - ] * ;
    }
    a.push(n);
    temp =  + bfs(len);
    if(temp<len)printf("%d",temp);
    else printf("-1");
}