题目描述
您将获得一个正整数n,写入时不带前导零(例如,数字04不正确)。
在一个操作中,您可以删除给定整数的任何数字,以便结果保持正整数而不带前导零。
用最少的操作找到一个平方数(4,9,16,,,,,,) 如果找不到输出 -1
例如 : 8314 最少的操作是删除3和4,得到81 ,需要两次操作。
输入
第一行包含一个整数n(1 ≤ n ≤ 2 ⋅ 10^9)。给出的数字没有前导零。
输出
输出执行此操作所需的最少操作数。如果无法从n得到一个平方数,则输出-1。
样例输入
8314
样例输出
2
参考代码
#include<stdio.h>
#include<math.h>
int num[11],book[11],pre0[11];
int tot=0,mintot=1000;
int getnum(int lenth)
{
int res=0;
for (int i=lenth;i>=1;i--)
{
if(!book[i]&&!pre0[i])
{
res*=10;
res+=num[i];
}
}
return res;
}
void solve(int lenth,int dep)
{
if(dep==lenth+1)
{
for (int i=lenth;i>=1;i--)
{
if(!book[i]&&num[i])break;
if(!book[i]&&!num[i])
{
pre0[i]=1;
tot++;
}
}
for (int i=lenth;i>=1;i--)
{
if(book[i])tot++;
}
if(tot==lenth)return;
double x=sqrt(getnum(lenth));
for (int i=lenth;i>=1;i--)pre0[i]=0;
if(x==(int)x)
{
if(tot<mintot)mintot=tot;
}
tot=0;
return;
}
book[dep]=1;
solve(lenth,dep+1);
book[dep]=0;
solve(lenth,dep+1);
}
int main()
{
//freopen("in.txt","r",stdin);
int cnt=0,m=0;
scanf("%d",&m);
while(m)
{
num[++cnt]=m%10;
m/=10;
}
solve(cnt,1);
if(mintot<1000)printf("%dn",mintot);
else printf("-1n");
return 0;
}
解析
暂无