Yet Another Multiple Problem

Time Limit: 40000/20000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)
Total Submission(s): 751 Accepted Submission(s): 209

Problem Description

There are tons of problems about integer multiples. Despite the fact that the topic is not original, the content is highly challenging. That’s why we call it “Yet Another Multiple Problem”.
In this problem, you’re asked to solve the following question: Given a positive integer n and m decimal digits, what is the minimal positive multiple of n whose decimal notation does not contain any of the given digits?

Input

There are several test cases.
For each test case, there are two lines. The first line contains two integers n and m (1 ≤ n ≤ 10⁴). The second line contains m decimal digits separated by spaces.
Input is terminated by EOF.

Output

For each test case, output one line “Case X: Y” where X is the test case number (starting from 1) while Y is the minimal multiple satisfying the above-mentioned conditions or “-1” (without quotation marks) in case there does not exist such a multiple.

Sample Input

2345 3

7 8 9

100 1

Sample Output

Case 1: 2345

Case 2: -1

解题思路：

输入n，m 和 m个字符（数字），要求找到一个最小的n的倍数，不含有给出的m个数字。如果不存在则输出-1

比较简单的bfs，利用所有能用的数字进行bfs即可。

每个节点记录三个值

c：末尾的那个数字

m：这个节点所代表的数字对n取模的值

f：父节点

对于一个节点，如果在其后面加一个数字i，那么新的m值=(m*10 + i)%n

显然，如果答案存在，那么我们第一个找到的m==0的节点就是答案，然后再用一个递归逆序输出就好。

可以发现，新节点的m的值只与父节点的m值有关，所以，对于相同的m，只有第一个出现m的节点是有用的。

当然，本题直接用字符串记录数字也是可以的，就不用递归输出了。因为用过的节点也要保留，所以没有使用STL的队列。

解题代码：

View Code

 1 // File Name: K - Yet Another Multiple Problem
 2 // Author: sheng
 3 // Created Time: 2013年04月24日 星期三 21时34分09秒
 4 
 5 #include <stdio.h>
 6 #include <string.h>
 7 
 8 const int Max = 10010;
 9 
10 struct node
11 {
12     int m, f;
13     char ch;
14 }d[Max], temp;
15 
16 bool k[10], h[Max];
17 int n, m;
18 
19 void out (int x)
20 {
21     if (x == -1)
22         return ;
23     out (d[x].f);
24     putchar (d[x].ch);
25 }
26 
27 int BFS (int ans)
28 {
29     int rear, top;
30     rear = top = 0;
31     for (int i = 1; i < 10; i ++ )
32     {
33         if (k[i])
34         {
35             temp.ch = i + '0';
36             temp.m = i%n;
37             h[temp.m] = false;
38             temp.f = -1;
39             d[rear++] = temp;
40             if (temp.m == 0)
41             {
42                 ans = rear - 1;
43                 break;
44             }
45         }
46     }
47     while (top < rear && ans == -1)
48     {
49         for (int i = 0; i < 10; i ++)
50         {
51             if (k[i])
52             {
53                 temp.ch = i + 48;
54                 temp.m = (d[top].m * 10 + i) % n;
55                 if (h[temp.m])
56                 {
57                     h[temp.m] = false;
58                     temp.f = top;
59                     d[rear ++] = temp;
60                     if (temp.m == 0)
61                     {
62                         ans = rear - 1;
63                         break;
64                     }
65                 }
66             }
67         }
68         top ++;
69     }
70     return ans;
71 }
72 
73 int main ()
74 {
75     int T = 0;
76     while (~scanf ("%d%d", &n, &m))
77     {
78         memset (h, true, sizeof (h));
79         memset (k, true, sizeof (k));
80         for (int i = 0; i < m; i ++)
81         {
82             int x;
83             scanf ("%d", &x);
84             k[x] = false;
85         }
86         int ans = -1;
87         printf ("Case %d: ", ++T);
88         ans = BFS(ans);
89         if (ans == -1)
90             printf ("-1");
91         else  out (ans);
92         printf ("\n");
93 
94     }
95     return 0;
96 }