超级密码

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


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

322 1037 0 12 101125 163A B C

Sample Output

110give me the bomb pleaseCCBHintHint Huge input, scanf is recommended.

 

题意：中文题面，就不解释了。

思路：BFS，由于数字太大了，所以每次记下取模的结果，然后找mod=0的最小值

 

#include #include #include #include #include #include #include using namespace std;
int a[20];
int vis[5555];
int n,c;
int m;
char str;
string tmp;
int flag;
struct Node{
string ans;
int mod;
}
f,t;
queueq;
void bfs(){
for(int i=1;
i<16;
i++) {
if(a[i]) {
int tt=i%n;
vis[tt]=1;
t.mod=tt;
t.ans=;
if(i<10) t.ans+=(i+'
0'
);
else t.ans+=(i-10+'
A'
);
q.push(t);
}
}
while(!q.empty()) {
t=q.front();
q.pop();
if(flag && t.ans.size()>tmp.size())continue;
if(t.mod==0) {
if(flag==0) tmp=t.ans;
flag=1;
if( tmp.size()>t.ans.size() || (tmp.size()==t.ans.size() && tmp>t.ans) ) tmp=t.ans;
}
for(int i=0;
i<16;
i++) {
if(a[i]==0) continue;
if(i<10) {
f=t;
f.ans+=(i+'
0'
);
f.mod=(f.mod*c+i)%n;
if( (vis[f.mod]==0 && f.ans.size()<=500) || f.mod==0 ) {
vis[f.mod]=1;
q.push(f);
}
}
else {
f=t;
f.ans+=(i-10+'
A'
);
f.mod=(f.mod*c+i)%n;
if( (vis[f.mod]==0 && f.ans.size()<=500) || f.mod==0 ) {
vis[f.mod]=1;
q.push(f);
}
}
}
}
}
int main(){
int T;
while(~scanf(%d,&T)) {
while(T--) {
scanf(%d %d,&n,&c);
scanf(%d,&m);
getchar();
memset(a,0,sizeof a);
memset(vis,0,sizeof vis);
for(int i=0;
ii++) str="">='
0'
&& str<='
9'
) a[str-'
0'
]=1;
else if(str>='
A'
&& str<='
F'
) a[str-'
A'
+10]=1;
getchar();
}
if(n==0) {
if(a[0]) printf(0);
else puts(give me the bomb please);
continue;
}
while(!q.empty()) q.pop();
flag=0;
bfs();
if(flag) cout< bomb="" else="" give="" me="" pre="" return="" the="">

 


 


 


 


 


 


>i++)>