首页 > 代码库 > 【DFS】Codeforces Round #402 (Div. 2) B. Weird Rounding

【DFS】Codeforces Round #402 (Div. 2) B. Weird Rounding

暴搜

#include<cstdio>
#include<algorithm>
using namespace std;
int n,K,Div=1,a[21],m,ans=100;
bool vis[21];
void calc(int now)
{
	int t=0;
	bool flag=0;
	for(int i=m;i>=1;--i) if(!vis[i])
	  {
	  	if((!flag) && a[i]==0)
	  	  return;
	  	t=t*10+a[i];
	  	flag=1;
	  }
	if(t%Div==0)
	  ans=min(ans,now);
}
void dfs(int cur,int now)
{
	if(cur>m)
	  {
	  	calc(now);
	  	return;
	  }
	vis[cur]=1;
	dfs(cur+1,now+1);
	vis[cur]=0;
	dfs(cur+1,now);
}
int main()
{
//	freopen("b.in","r",stdin);
	scanf("%d%d",&n,&K);
	bool flag=0;
	while(n)
	  {
	  	a[++m]=n%10;
	  	if(a[m]==0)
	  	  flag=1;
	  	n/=10;
	  }
	if(flag)
	  ans=m-1;
	for(int i=1;i<=K;++i)
	  Div*=10;
	dfs(1,0);
	printf("%d\n",ans);
	return 0;
}

【DFS】Codeforces Round #402 (Div. 2) B. Weird Rounding