2012Chhengdu K - Yet Another Multiple Problem

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<cmath>
 5 #define M(a,b) memset(a,b,sizeof(a))
 6 #define INF 0x3f3f3f3f
 7 
 8 using namespace std;
 9 
10 int n,m;
11 
12 int pre[1000005],num[1000005];
13 int can[15];
14 int que[1000005];
15 int vis[1000005];
16 int res[1000005];
17 
18 int bfs()
19 {
20     int head = -1;
21     int tail = 0;
22     M(vis,0);
23     que[0] = 0;
24     for(int i = 1;i<10;i++)
25     {
26         if(!can[i])
27         {
28             if(i%n==0) {num[i] = i,pre[i] = 0; return i;}
29             else num[i] = i,pre[i] = 0, vis[i] = 1, que[tail] = i,tail++;
30         }
31     }
32     while(head<tail)
33     {
34         head++;
35         int tmp = que[head];
36         //cout<<tmp<<endl;
37         for(int i = 0;i<10;i++)
38         {
39             if(i==0&&tmp==0) continue;
40             //cout<<i<<endl;
41             if(!can[i])
42             {
43                 int u = tmp*10+i;
44                 int t = u%n;
45                 if(!vis[t])
46                 {
47                 if(t==0) {pre[u] = tmp, num[u] = i;return u;}
48                 else{
49                     //cout<<t<<‘ ‘<<i<<endl;
50                     pre[t] = tmp, num[t] = i;
51                     vis[t] = 1;
52                     que[tail] = t;
53                     tail++;
54                 }
55                 }
56             }
57         }
58     }
59     return -1;
60 }
61 
62 int main()
63 {
64     int cas = 1;
65     while(scanf("%d%d",&n,&m)==2)
66     {
67         M(pre,0);
68         M(num,0);
69         M(can,0);
70         for(int i = 0;i<m;i++)
71         {
72             int a;
73             scanf("%d",&a);
74             can[a] = 1;
75         }
76         pre[0] = -1;
77         int ans = bfs();
78         if(m==10) {printf("Case %d: -1\n",cas++); continue;}
79         printf("Case %d: ",cas++);
80         if(ans == -1) puts("-1");
81         else{
82             int cnt = 0;
83             for(int i = ans;pre[i]!=-1;i = pre[i])
84                 res[cnt++] = num[i];
85             for(int i = cnt-1;i>0;i--)
86                 printf("%d",res[i]);
87             printf("%d\n",res[0]);
88         }
89     }
90     return 0;
91 }

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<cmath>
 5 #include<queue>
 6 #define M(a,b) memset(a,b,sizeof(a))
 7 #define INF 0x3f3f3f3f
 8 
 9 using namespace std;
10 
11 int n,m;
12 
13 struct node{
14    int num;
15    string c;
16 };
17 queue<node> que;
18 int can[15];
19 int vis[1000005];
20 int res;
21 
22 node bfs()
23 {
24     while(!que.empty()) que.pop();
25     M(vis,0);
26     for(int i = 1;i<10;i++)
27     {
28         if(!can[i])
29         {
30             node tp;
31             tp.c = "";
32             tp.num = 0;
33             if(i%n==0) {char ch = i+‘0‘; tp.c += ch; return tp;}
34             else {
35                 tp.num = i%n;
36                 char ch = i+‘0‘;
37                 tp.c += ch;
38                 vis[i] = 1;
39                 que.push(tp);
40                 //cout<<tp.c<<endl;
41             }
42         }
43     }
44     while(!que.empty())
45     {
46         node tmp = que.front();
47         que.pop();
48         //cout<<tmp.c<<endl;
49         for(int i = 0;i<10;i++)
50         {
51             if(!can[i])
52             {
53                 int t = (tmp.num*10+i)%n;
54                 if(!vis[t])
55                  {
56                    if(t==0) {char ch = i+‘0‘; tmp.c+=ch; return tmp;}
57                    else
58                     {
59                        node tp;
60                        tp.num = t;
61                        char ch = i+‘0‘;
62                        tp.c = tmp.c+ch;
63                        //cout<<tp.num<<endl;
64                        vis[t] = 1;
65                        que.push(tp);
66                     }
67                 }
68             }
69         }
70     }
71     res = -1;
72     node none;
73     return none;
74 }
75 
76 int main()
77 {
78     int cas = 1;
79     while(scanf("%d%d",&n,&m)==2)
80     {
81         res = 0;
82         M(can,0);
83         for(int i = 0;i<m;i++)
84         {
85             int a;
86             scanf("%d",&a);
87             can[a] = 1;
88         }
89         if(m==10) {printf("Case %d: -1\n",cas++); continue;}
90         node ans = bfs();
91         printf("Case %d: ",cas++);
92         if(res == -1) puts("-1");
93         else cout<<ans.c<<endl;
94     }
95     return 0;
96 }

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<cmath>
 5 #include<queue>
 6 #define M(a,b) memset(a,b,sizeof(a))
 7 #define INF 0x3f3f3f3f
 8 
 9 using namespace std;
10 
11 int n,m;
12 
13 int can[15];
14 int vis[1000005];
15 int res;
16 
17 queue<pair<string,int> > rec;
18 
19 string bfs()
20 {
21     while (!rec.empty()) rec.pop();
22     pair<string,int>init;
23     init.first="";init.second=0;
24     rec.push(init);
25     int i;
26     while (!rec.empty())
27     {
28         pair<string,int> curr=rec.front();
29         for (i=0;i<10;i++)
30         {
31             if (curr.first.length()==0&&i==0) continue;
32             if (can[i]) continue;
33             char ch=‘0‘+i;
34             string ss=curr.first+ch;
35             int x=(curr.second*10+i)%n;
36             if (!vis[x])
37             {
38                 if (x==0) return ss;
39                 pair<string,int>u;
40                 u.first=ss;u.second=x;
41                 rec.push(u);
42                 vis[x]=1;
43             }
44         }
45         rec.pop();
46     }
47     return "-1";
48 }
49 
50 int main()
51 {
52     int cas = 1;
53     while(scanf("%d%d",&n,&m)==2)
54     {
55         M(can,0);
56         M(vis,0);
57         for(int i = 0;i<m;i++)
58         {
59             int a;
60             scanf("%d",&a);
61             can[a] = 1;
62         }
63         string ans = bfs();
64         printf("Case %d: ",cas++);
65         cout<<ans<<endl;
66     }
67     return 0;
68 }