poj 1465

2272 단어 structinputeachoutput
program that, given a natural number N between 0 and 4999 (inclusively), and M distinct decimal digits X1,X2..XM (at least one), finds the smallest strictly positive multiple of N that has no other digits besides X1,X2..XM (if such a multiple exists).
Input
The input has several data sets separated by an empty line, each data set having the following format: 
On the first line - the number N 
On the second line - the number M 
On the following M lines - the digits X1,X2..XM.
Output
For each data set, the program should write to standard output on a single line the multiple, if such a multiple exists, and 0 otherwise. 
An example of input and output:
Sample Input
22
3
7
0
1

2
1
1
Sample Output
110
0
Source
Southeastern Europe 2000
 
/*이 광수는 날카롭군요. 우선 왜 광수가 가장 좋은 결과를 얻을 수 있는지 증명해야 합니다. 첫 번째가 0인 상황을 없애야 합니다. 그래서 매번 검색하는 숫자는 어릴 때부터 큰 순서에 따라 가장 좋은 결과를 얻을 수 있습니다. 그래서 광수로 할 수 있습니다. 그러면 지금 몇 가지 문제를 해결해야 합니다. 우선 상태 수가 너무 많은 상황이 발생할 수 있습니다. 여기에 강력한 가지치기가 있습니다. 예를 들어 A=MX+R B=NX+R 가설 A,B는 X의 여수가 같다면 (10*A+d[i])% x(10*B+d[i])% x의 의미는 같기 때문에 여수가 나타나지 않은 경우에만 검색의 대기열에 넣는 또 다른 문제는 마지막 답안이 방대한 자릿수를 나타낼 수 있다는 것이다. 만약에 여기에 높은 정밀도를 사용하면 너무 번거롭다.나는 정적 바늘을 사용한다.그리고 N=0을 단독으로 처리한 경우 */#include#include#includeusingnamespacestd;const int maxn=5010; struct node { int digit; int yu; int pre; }que[maxn]; int n,m; int d[100]; bool flag[maxn]; void output(node t) { if(t.pre!=-1) { output(que[t.pre]); printf("%d",t.digit); } } void bfs() { int front,rear,r; bool f=0; memset(flag,0,sizeof(flag)); que[0].digit=0; que[0].yu=0; que[0].pre=-1; front=0; rear=1; while(front0)) { flag[r]=1; t.digit=d[i]; t.yu=r; t.pre=front; que[rear++]=t; if(r==0) { output(t); printf("/n"); f=true; break; } } if(f) break; } front++; if(f) break; } if(!f) { printf("0/n"); } } int main() { while(scanf("%d",&m)!=EOF) { scanf("%d",&n); for(int i=0;i

좋은 웹페이지 즐겨찾기