C. Make a Square
time limit per test2 seconds
memory limit per test256 megabytes
inputstandard input
outputstandard output
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⋅109). 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
inputCopy
8314
outputCopy
2
inputCopy
625
outputCopy
0
inputCopy
333
outputCopy
-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.
题意：
给你一个字符串，让你删除最少的字符串个数，使其剩余的字符串代表的数字没有前导0，并且是一个数的平方数。
思路：
因为字符串的长度是 2e9 ，我们知道 y的最大范围 sqrt(2e9) 那么我们显然可以枚举每一个y，把他的平方数转为字符串（长度最大为9），去和给定的字符串进行匹配，检测是否可以是给定字符串的子序列，并维护满足子序列的不同字符个数的最小值就是答案。
时间复杂度 O( 9 * sqrt(2e9 ) )
细节见代码：
#include <bits/stdc++.h>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <vector>
#include <iomanip>
#define ALL(x) (x).begin(), (x).end()
#define rt return
#define dll(x) scanf("%I64d",&x)
#define xll(x) printf("%I64d\n",x)
#define sz(a) int(a.size())
#define all(a) a.begin(), a.end()
#define rep(i,x,n) for(int i=x;i<n;i++)
#define repd(i,x,n) for(int i=x;i<=n;i++)
#define pii pair<int,int>
#define pll pair<long long ,long long>
#define gbtb ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
#define MS0(X) memset((X), 0, sizeof((X)))
#define MSC0(X) memset((X), '\0', sizeof((X)))
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define eps 1e-6
#define gg(x) getInt(&x)
#define chu(x) cout<<"["<<#x<<" "<<(x)<<"]"<<endl
using namespace std;
typedef long long ll;
ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
ll lcm(ll a,ll b){return a/gcd(a,b)*b;}
ll powmod(ll a,ll b,ll MOD){ll ans=1;while(b){if(b%2)ans=ans*a%MOD;a=a*a%MOD;b/=2;}return ans;}
inline void getInt(int* p);
const int maxn=1000010;
const ll inf=1e18+7;
/*** TEMPLATE CODE * * STARTS HERE ***/
string S(ll n){stringstream ss;string s;ss<<n;ss>>s;return s;}
ll N(string s){stringstream ss;ll n;ss<<s;ss>>n;return n;}
string a;
int main()
{
//freopen("D:\\common_text\\code_stream\\in.txt","r",stdin);
//freopen("D:\\common_text\\code_stream\\out.txt","w",stdout);
cin>>a;
ll ans=inf;
int len=a.length();
ll y=1ll;
while(1)
{
ll x=y*y;
string str=S(x);
int slen=str.size();
if(slen>len)
break;
int id=0;
for(int i=0;i<len;++i)
{
if(a[i]==str[id])
{
id++;
}
}
if(id==slen)
{
ans=min(ans,1ll*len-slen);
}
y++;
}
if(ans==inf)
{
ans=-1;
}
cout<<ans<<endl;
return 0;
}
inline void getInt(int* p) {
char ch;
do {
ch = getchar();
} while (ch == ' ' || ch == '\n');
if (ch == '-') {
*p = -(getchar() - '0');
while ((ch = getchar()) >= '0' && ch <= '9') {
*p = *p * 10 - ch + '0';
}
}
else {
*p = ch - '0';
while ((ch = getchar()) >= '0' && ch <= '9') {
*p = *p * 10 + ch - '0';
}
}
}