HDU 1226スーパーパスワード(ワイド検索+メモリ検索)
3645 ワード
B-スーパーパスワード
Time Limit:10000MS Memory Limit:32768KB 64bit IO Format:%I64d & %I64u
Submit
Status
Description
Ignatiusは1週間かけてやっと伝説の宝物を見つけました.宝物は1つの部屋に置かれています.部屋のドアはパスワードでロックされています.ドアのそばの壁にはパスワードに関するヒントがあります.
パスワードはC進数であり、与えられたM個の数字のみで構成され、同時にパスワードは与えられた10進数の整数N(0<=N<=5000)の正の整数倍(複数の条件を満たす数がある場合、最小はパスワード)であり、このようなパスワードが存在する場合、入力するとドアが開き、このようなパスワードが存在しない場合......じゃ、ドアを爆破しましょう.
注意:宝の歴史が長いため、当時のシステムは最大500ビットのパスワードしか保存できなかった.したがって、得るパスワードの長さが500より大きくてもドアを開けることができない場合、パスワードは存在しないと考えられる.
Input
入力データの1行目は、テストデータの数を示す整数T(1<=T<=300)である.各試験データの1行目は、2つの整数N(0<=N<=5000)とC(2<=C<=16)である、ここで、Nは、問題記述における所定の10進数の整数を表し、Cは、暗号の進数である.テストデータの2行目は、暗号を構成する数字の数を表す整数M(1<=M<=16)であり、次に暗号を構成する数字を表すM数字である.2つのテストデータの間に空の行が分離されます.
注意:与えられたM個の数字のうち、10を超える数がある場合、Aで10、Bで11、Cで12、Dで13、Eで14、Fで15を表すことにする.入力データが合法であることを保証します.
Output
テストデータのセット毎に要求するパスワードがある場合はそのパスワードを出力し、パスワードが存在しない場合は「give me the bomb please」を出力.
注意:パスワードを構成する数字は必ずしもすべて使わなければならないとは限らない.パスワードは非常に長い可能性があります.整数変数でパスワードを保存しようとしないでください.パスワードの最上位は0ではないことを保証します(パスワード自体が0でない限り).
Sample Input
Sample Output
Hint
Time Limit:10000MS Memory Limit:32768KB 64bit IO Format:%I64d & %I64u
Submit
Status
Description
Ignatiusは1週間かけてやっと伝説の宝物を見つけました.宝物は1つの部屋に置かれています.部屋のドアはパスワードでロックされています.ドアのそばの壁にはパスワードに関するヒントがあります.
パスワードはC進数であり、与えられたM個の数字のみで構成され、同時にパスワードは与えられた10進数の整数N(0<=N<=5000)の正の整数倍(複数の条件を満たす数がある場合、最小はパスワード)であり、このようなパスワードが存在する場合、入力するとドアが開き、このようなパスワードが存在しない場合......じゃ、ドアを爆破しましょう.
注意:宝の歴史が長いため、当時のシステムは最大500ビットのパスワードしか保存できなかった.したがって、得るパスワードの長さが500より大きくてもドアを開けることができない場合、パスワードは存在しないと考えられる.
Input
入力データの1行目は、テストデータの数を示す整数T(1<=T<=300)である.各試験データの1行目は、2つの整数N(0<=N<=5000)とC(2<=C<=16)である、ここで、Nは、問題記述における所定の10進数の整数を表し、Cは、暗号の進数である.テストデータの2行目は、暗号を構成する数字の数を表す整数M(1<=M<=16)であり、次に暗号を構成する数字を表すM数字である.2つのテストデータの間に空の行が分離されます.
注意:与えられた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.#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<queue>
#include<string>
using namespace std;
const int INF=0x3f3f3f3f;
const int MAXN=20+5;
int done[5005],n,type,m,i,win;
int da[17];
struct node
{
int key,pre,yu,place;
}p[100000];
void showpath(int id)
{
if(!id)return ;
showpath(p[id].pre);
if(p[id].key>=10)printf("%c",p[id].key-10+'A');
else printf("%d",p[id].key);
}
void bfs()
{
win=0;
queue<int>q;
memset(done,0,sizeof(done));
int cnt=0;
p[0].pre=-1;
p[0].yu=0;
p[0].place=0;
q.push(cnt++);
while(!q.empty())
{
int id=q.front();q.pop();
if(p[id].place==500)return ;
for(i=0;i<m;i++)
{
if(p[id].yu==0&&da[i]==0)continue;
int yu=(p[id].yu*type+da[i])%n;
if(done[yu])continue;
if(yu==0)
{
win=1;
showpath(id);
if(da[i]>=10)printf("%c
",da[i]-10+'A');
else printf("%d
",da[i]);
return ;
}
done[yu]=1;
p[cnt].key=da[i];
p[cnt].yu=yu;
p[cnt].pre=id;
p[cnt].place=p[id].place+1;
q.push(cnt++);
}
}
}
int main()
{
int N;char c,s[3];
//freopen("123.txt","r",stdin);
cin>>N;
while(N--)
{
scanf("%d%d%d",&n,&type,&m);
gets(s);
for(i=0;i<m;i++)
{
scanf("%c%*c",&c);
if(c>='A'&&c<='Z')da[i]=10+c-'A';
else da[i]=c-'0';
}
sort(da,da+m);
while(da[m-1]>=type)
{
m--;
if(!m)break;
}
if(!m){printf("give me the bomb please
");continue;}
if(n==0)
if(da[0]==0){printf("0
");continue;}
else {printf("give me the bomb please
");continue;}
bfs();
if(!win)printf("give me the bomb please
");
}
return 0;
}