HDOJ 1226 超级密码

超级密码

Time Limit: 20000/10000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 1492 Accepted Submission(s): 445

Problem Description

Ignatius花了一个星期的时间终于找到了传说中的宝藏,宝藏被放在一个房间里,房间的门用密码锁起来了,在门旁边的墙上有一些关于密码的提示信息:
密码是一个C进制的数,并且只能由给定的M个数字构成,同时密码是一个给定十进制整数N(0<=N<=5000)的正整数倍(如果存在多个满足条件的数,那么最小的那个就是密码),如果这样的密码存在,那么当你输入它以后门将打开,如果不存在这样的密码......那就把门炸了吧.

注意:由于宝藏的历史久远,当时的系统最多只能保存500位密码.因此如果得到的密码长度大于500也不能用来开启房门,这种情况也被认为密码不存在.

Input

输入数据的第一行是一个整数T(1<=T<=300),表示测试数据的数量.每组测试数据的第一行是两个整数N(0<=N<=5000)和C(2<=C<=16),其中N表示的是题目描述中的给定十进制整数,C是密码的进制数.测试数据的第二行是一个整数M(1<=M<=16),它表示构成密码的数字的数量,然后是M个数字用来表示构成密码的数字.两个测试数据之间会有一个空行隔开.

注意:在给出的M个数字中,如果存在超过10的数,我们约定用A来表示10,B来表示11,C来表示12,D来表示13,E来表示14,F来表示15.我保证输入数据都是合法的.

Output

对于每组测试数据,如果存在要求的密码,则输出该密码,如果密码不存在,则输出"give me the bomb please".

注意:构成密码的数字不一定全部都要用上;密码有可能非常长,不要试图用一个整型变量来保存密码;我保证密码最高位不为0(除非密码本身就是0).

Sample Input

3
22 10
3
7 0 1

2 10
1
1

25 16
3
A B C

Sample Output

110
give me the bomb please
CCB

Hint

Hint

Huge input, scanf is recommended.

Author

Ignatius.L

Source

杭州电子科技大学第三届程序设计大赛

Recommend

Ignatius.L

r= k （mod c）則（k*p+a）（mod c）=（r*p+a）（mod c）

若是某个数&＃20540;序列的余数为r.....若是某个余数已经被机关过...那么后面获得的必然是与本来机关过的余数序列雷同的序列而由BFS的性质.最短的必然是最先被机关出来的..所以.....先到先得!（每一位应用什么数字都是不变的哦.....就是在同一个数&＃20540;凑集内...）. 若是看不懂看下面的

例如若是 k1％c==k1k2％c 则 k1k3％c==k1k2k3％c

再特别一点的比如 3％4==3 27％4==3 则 31％4==271％4 ，32％4==272％4 ，33％4==273％4...............

我们请求得的数是n的整数倍即余数为0 则取余数为0的数中的最小的那个即可

若是请求余数为k的数只请求出最短的序列因为n<5000余数最多有5000个用BFS搜刮余数第一次呈现的地位就是最短的序列从中我们找出余数为0对应的最短的序列即可

结论：只要某种余数曾经呈现过.那么这种余数就不须要再呈现..... 直到找到余数为0 或者长度大于500就退出

  1 #include <iostream>
  2 #include <cstring>
  3 #include <cstdio>
  4 #include <queue>
  5 
  6 using namespace std;
  7 
  8 const int maxn=505;
  9 const int maxm=5006;
 10 
 11 bool mod[maxm];
 12 char arr[22];
 13 int digit[22];
 14 
 15 
 16 struct Node
 17 {
 18     char str[maxn];
 19     int len;
 20 }ans;
 21 
 22 int N,C,M;
 23 
 24 int judge(Node X)
 25 {
 26     int sum=0;
 27     int len=X.len;
 28     int OK=0;
 29     for(int i=0;i<len;i++)
 30     {
 31         if(X.str[i]!='0')
 32         {
 33             OK=1;
 34             break;
 35         }
 36     }
 37     if(!OK)  return 5005;
 38     for(int i=0;i<len;i++)
 39     {
 40         if(X.str[i]>='0'&&X.str[i]<='9')
 41         {
 42          sum=(sum*C+(X.str[i]-'0'))%N;
 43         }
 44         else if(X.str[i]>='A'&&X.str[i]<='F')
 45         {
 46             sum=(sum*C+(X.str[i]-'A'+10))%N;
 47         }
 48     }
 49     sum=sum%N;
 50     return sum;
 51 }
 52 
 53 queue<Node> q;
 54 
 55 int bfs()
 56 {
 57 
 58     Node x,y;
 59 
 60     while(!q.empty())
 61     {
 62 
 63         y=q.front();
 64         q.pop();
 65         int MOD1;
 66 
 67       //  if(y.len==3&&y.str[0]=='1'&&y.str[1]=='1'&&y.str[0]=='0')  cout<<"miaomiaoishere
";
 68 
 69         if((MOD1=judge(y))==0)
 70         {
 71             ans=y;
 72             int len=ans.len;
 73             for(int i=0;i<len;i++)
 74                 printf("%c",ans.str[i]);
 75             putchar(10);
 76             return 1;
 77         }
 78         int zero=0;
 79 //        if(y.len==1) zero=1;
 80         for(int i=zero;i<16;i++)
 81         {
 82             if(digit[i])
 83             {
 84                 x=y;
 85                 if(i>=0&&i<10)
 86                   x.str[x.len]=i+'0';
 87                 else if(i>=10&&i<=15)
 88                   x.str[x.len]=i-10+'A';
 89                 x.len=x.len+1;
 90                 int MOD2=judge(x);
 91                 if(x.len+1<=500&&mod[MOD2]==false&&MOD2!=5005)
 92                 {
 93                     mod[MOD2]=true;
 94                     q.push(x);
 95                 }
 96             }
 97         }
 98     }
 99     return 0;
100 }
101 
102 int main()
103 {int T;
104 scanf("%d",&T);
105 while(T--)
106 {
107     memset(mod,false,sizeof(mod));
108     memset(digit,0,sizeof(digit));
109     while(!q.empty())  q.pop();
110 
111     scanf("%d%d%d",&N,&C,&M);
112     getchar();
113     for(int i=0;i<M;i++)
114     {
115        scanf("%c",&arr[i]);
116        getchar();
117        if(arr[i]<='9'&&arr[i]>='0')
118          digit[arr[i]-'0']=1;
119        else if(arr[i]<='F'&&arr[i]>='A')
120         digit[arr[i]-'A'+10]=1;
121     }
122     Node xt;
123     for(int i=0;i<=16;i++)
124     {
125         if(digit[i])
126         {
127             if(i>=0&&i<10)
128               xt.str[0]=i+'0';
129             else if(i>=10&&i<=15)
130               xt.str[0]=i-10+'A';
131             xt.len=1;
132             q.push(xt);
133   //          int MOD=judge(xt);
134   //          mod[MOD]=true;
135         }
136     }
137   //  cout<<q.size()<<"----------
";
138   //  getchar();
139 
140     if(N==0)
141     {
142         if(digit[0]) puts("0");
143         else  puts("give me the bomb please");
144     }
145     else
146     {
147         if(bfs())
148         {
149         }
150         else
151         puts("give me the bomb please");
152     }
153 
154 }
155 
156     return 0;
157 }