codeforces C. Make a Square

65 阅读 0 评论 43 点赞

我是靠谱客的博主耍酷未来，最近开发中收集的这篇文章主要介绍codeforces C. Make a Square，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

题目网址：http://codeforces.com/problemset/problem/962/C

You are given a positive integer $n 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 n$ to make from it the square of some positive integer or report that it is impossible.

An integer $x x$ is the square of some positive integer if and only if $x = y^{2} x=y2$ for some positive integer $y y$ .

Input

The first line contains a single integer $n n$ ( $1 \leq n \leq 2 \cdot 10^{9} 1\leqn\leq2\cdot109$ ). The number is given without leading zeroes.

Output

If it is impossible to make the square of some positive integer from $n n$ , print -1. In the other case, print the minimal number of operations required to do it.

Examples

input

Copy
8314

output

Copy
2

input

Copy
625

output

Copy
0

input

Copy
333

output

Copy
-1

Note

In the first example we should delete from $83148314$ the digits $33$ and $44$ . After that $83148314$ become equals to $8181$ , which is the square of the integer $99$ .

In the second example the given $625625$ is the square of the integer $2525$ , so you should not delete anything.

In the third example it is impossible to make the square from $333333$ , so the answer is -1.

题目的大致意思是，给你一个数，然后让你删除其中的几位数，使它变成一个完全平方数，求它的最少删除几个数可以变成完全平方数。

理解懂题意后，就想到了暴搜，但是不敢写，想了半天也没想到其他方法，就试着写一下，结果不加优化都还可以可以过得。

首先说一下思想吧，就是枚举它每次可以截取的每一位，然后再去下一层接着去枚举，这样依次着搜索。本来我是用char数组写的，真的很恶心，也很麻烦，后来突然想到可以用string，可以方便很多很多，用一个substr来截取它，然后搜索。还要打一个map的表，先把2e9的完全平方数打出来，方便查询。

但是还是不是那么容易对的，wa了几发，因为在截取位的时候，我们需要用一个搜索的递归变量来标识这个数现在已经删除了几位数字，有一种情况！就是前导零的时候，比如 101 、 70000729这种数字，都是需要处理前导零的，因为你截取7以后，在我手写的get数字的时候会直接变成729，所以就变成了删除一位数，但是实际上需要删除5位，所以得到一个字符串以后，判断一下前导零，如果有的话，就把它也加到标记变量中（其实处理方式还有很多种，看个人思维怎么想都可以的）

大致处理就是这样了，下面是代码：

#include <bits/stdc++.h>
using namespace std;
const int Maxn = 4e4 + 5000;
int vis[Maxn];
string str;
int ans = 0,flag = 0;
map<long long,bool>mp;
void Init() {
mp.clear();
for(int i = 1; i < Maxn; i++) {
mp[i * i] = 1;
}
return ;
}
long long getnum(string s) {
long long ans1 = 0;
for(int i = 0; i < s.size(); i++)
ans1 = ans1 * 10 + s[i] - '0';
return ans1 ;
}
void dfs(string s,int cnt) {
if(mp[getnum(s)]) {
int id = 0;
if(s[0] ==
'0')
while(s[id] == '0')
id++;
flag = 1;
ans = min(cnt + id,ans);
}
for(int i = 0; i < s.size(); i++) {
string ss = s.substr(0,i) + s.substr(i + 1,s.size() - i - 1);
if(ss != "")
dfs(ss,cnt + 1);
}
}
int main() {
Init();
while(cin >> str) {
ans = 999999,flag
= 0;
dfs(str,0);
if(flag) cout << ans << endl;
else
cout << - 1
<< endl;
}
return 0;
}