HDu--1226(bfs+レコードパス)
4416 ワード
スーパーパスワード
Time Limit: 20000/10000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others) Total Submission(s): 3361 Accepted Submission(s): 1075
Problem Description
Ignatiusは1週間かけてやっと伝説の宝物を見つけました.宝物は1つの部屋に置かれています.部屋のドアはパスワードでロックされています.ドアのそばの壁にはパスワードに関するヒントがあります.
パスワードはC進数で、与えられたM個の数字でしか構成できないが、パスワードは与えられた10進数の整数N(0<=N<=5000)の正の整数倍(複数の条件を満たす数があれば、最小はパスワード)であり、このようなパスワードが保存されている場合は、入力するとドアが開き、このようなパスワードが存在しない場合は...ドアを爆破しましょう.
注意:宝の歴史が古いため、当時のシステムは最大500ビットのパスワードしか保存できなかった.そのため、得られたパスワードの長さが500より大きくてもドアを開けることができなかった場合、パスワードは存在しないと考えられている.
Input
入力データの最初の行は1つの整数T(1<=T<=300)であり、テストデータの数を表す.各テストデータの最初の行は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
Time Limit: 20000/10000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others) Total Submission(s): 3361 Accepted Submission(s): 1075
Problem Description
Ignatiusは1週間かけてやっと伝説の宝物を見つけました.宝物は1つの部屋に置かれています.部屋のドアはパスワードでロックされています.ドアのそばの壁にはパスワードに関するヒントがあります.
パスワードはC進数で、与えられたM個の数字でしか構成できないが、パスワードは与えられた10進数の整数N(0<=N<=5000)の正の整数倍(複数の条件を満たす数があれば、最小はパスワード)であり、このようなパスワードが保存されている場合は、入力するとドアが開き、このようなパスワードが存在しない場合は...ドアを爆破しましょう.
注意:宝の歴史が古いため、当時のシステムは最大500ビットのパスワードしか保存できなかった.そのため、得られたパスワードの長さが500より大きくてもドアを開けることができなかった場合、パスワードは存在しないと考えられている.
Input
入力データの最初の行は1つの整数T(1<=T<=300)であり、テストデータの数を表す.各テストデータの最初の行は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
Tips： A<B A%n==B%n A B。
:
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include<algorithm>
#define MAXN 5000// 5000
#define MAXM 17
#define MAXC 17
using namespace std;
int num[MAXM];
bool status[MAXN];
int basis, sys, n;
struct Node{
int mod;
int dig;
int pre;//
int step;//
}Queue[MAXN], init = { 0, 0, -1 };
void echo(int x){
if (Queue[x].pre == -1) return;
else echo(Queue[x].pre);
if (Queue[x].dig <= 9)
printf("%d", Queue[x].dig);
else
putchar(Queue[x].dig + 'A' - 10);
}
bool bfs(){
Node curr, next;
int front = 0, rear = 1, res;
Queue[0] = init;
memset(status, 0, sizeof(status));
while (front != rear){
curr = Queue[front];
for (int i = 0; i < n; i++){// n
res = (curr.mod * sys + num[i]) % basis;//sys
if (status[res] || (curr.pre == -1 && num[i] == 0) || curr.step >= 500) continue; // 0, 500
status[res] = 1;//
Queue[rear].mod = res;
Queue[rear].dig = num[i];
Queue[rear].pre = front;
Queue[rear].step = curr.step + 1;
if (res == 0) { echo(rear); putchar('
'); return true; }
rear++;
}
front++;
}
return false;
}
int main(){
int t;
char tmp[3];
scanf("%d", &t);
while (t--){
scanf("%d%d%d", &basis, &sys, &n);
for (int i = 0; i < n; i++){
scanf("%s", tmp);
if (tmp[0] <= '9' && tmp[0] >= '0') num[i] = tmp[0] - '0';
else if (tmp[0] <= 'F' && tmp[0] >= 'A') num[i] = tmp[0] - 'A' + 10;
}
sort(num,num+n);// ,
if (basis == 0){
if (num[0] == 0)
printf("0
");
else
printf("give me the bomb please
");
continue;
}
if (!bfs())
printf("give me the bomb please
");
}
return 0;
}