Find The Multiple
| Time Limit: 1000MS | Memory Limit: 10000K | |||
| Total Submissions: 14622 | Accepted: 5938 | Special Judge | ||
Description
Given a positive integer n, write a program to find out a nonzero multiple m of n whose decimal representation contains only the digits 0 and 1. You may assume that n is not greater than 200 and there is a corresponding m containing no more than 100 decimal digits.
Input
The input file may contain multiple test cases. Each line contains a value of n (1 <= n <= 200). A line containing a zero terminates the input.
Output
For each value of n in the input print a line containing the corresponding value of m. The decimal representation of m must not contain more than 100 digits. If there are multiple solutions for a given value of n, any one of them is acceptable.
Sample Input
2 6 19 0
Sample Output
10100100100100100100111111111111111111
就是找倍数，bfs 这题 就是宽搜，我打/*号的是深搜的代码 ，但是很慢，也过不了，很容易就RUNTIME去了！
#include<iostream>
#include<stdio.h>
#include<stack>
#include<string.h>
using namespace std;
stack<int > q;
struct hal{
int x,leave,floor,front;
}l[300000];
int visit[300];
int n,re;
bool init(int num,int flag)
{
/*
l[num].x=flag;
if(flag==0)
{
l[num].leave=(l[num>>1].leave*10)%n;
if(visit[l[num].leave])
return false;
visit[l[num].leave]=1;
l[num].floor=l[num>>1].floor+1;
if(l[num].leave==0)
{
re=num;
return true;
}
if(l[num].floor>200)
return false;
}
else if(flag==1)
{
l[num].leave=(l[num>>1].leave*10+1)%n;
if(visit[l[num].leave])
return false;
visit[l[num].leave]=1;
l[num].floor=l[num>>1].floor+1;
if(l[num].leave==0)
{
re=num;
return true;
}
if(l[num].floor>200)
return false;
}
else if(flag==-1)
{
l[num].leave=1;
l[num].x=-1;
l[num].floor=1;
}
if(init(num<<1,0))
return true;
if(init(num<<1|1,1))
return true;
return false;
*/
int t,w,j;
t=w=1;
l[t].x=-1;
l[t].leave=1;
l[t].floor=1;
l[t].front=-1;
while(t<=w)
{
for(j=0;j<=1;j++)
{
l[++w].floor=l[t].floor+1;
l[w].front=t;
l[w].x=j;
if(j==0)
l[w].leave=(l[t].leave*10)%n;
else
l[w].leave=(l[t].leave*10+1)%n;
if(visit[l[w].leave])
{
w--;
continue;
}
visit[l[w].leave]=1;
if(l[w].leave==0)
{
re=w;
return true;
}
if(l[w].floor>200)
{
continue;
}
}
t++;
}
return false;
}
bool bfs(int e)
{
while(l[e].x!=-1)
{
q.push(l[e].x);
e=l[e].front;
}
printf("1");
while(!q.empty())
{
printf("%d",q.top());
q.pop();
}
printf("
");
return true;
}
int main ()
{
while(scanf("%d",&n)!=EOF&&n)
{
memset(visit,0,sizeof(visit));
visit[1]=1;
l[1].leave=-1;
init(1,-1);
//printf("%d",re);
bfs(re);
}
return 0;
}