hdu1226 BFS
スーパーパスワード
Time Limit : 20000/10000ms (Java/Other) Memory Limit : 65536/32768K (Java/Other)
Total Submission(s) : 3 Accepted Submission(s) : 1
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
a,bを加えた残数は同じであり,a
それから広搜~~余数が同じなら必ず小さいのを探し出して、余数に対してマークの配列を开いて、余数が初めて现れて、マークして、行列に参加して、それからのは参加しません
Time Limit : 20000/10000ms (Java/Other) Memory Limit : 65536/32768K (Java/Other)
Total Submission(s) : 3 Accepted Submission(s) : 1
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 CCBHuge input, scanf is recommended.HintHint
Author
Ignatius.L
Source
杭州电子科技大学第三届程序设计大赛
先给出大数求模的代码
int judge(node &a)
{
int tmp=0;
int i;
for(i=0;ia,bを加えた残数は同じであり,a
それから広搜~~余数が同じなら必ず小さいのを探し出して、余数に対してマークの配列を开いて、余数が初めて现れて、マークして、行列に参加して、それからのは参加しません
#include
#include
#include
#include
#define INF 0x3f3f3f3f
#define BUG printf("here!
")
using namespace std;
int num[17];
int n,c,m;
struct node
{
int base[505];
int len;
};
int vis[5005];
void print(node &a)
{
int i;
for(i=0;i q;
int i;
for(i=1;i<16;i++)
{
if(num[i])
{
x.base[0]=i;
x.len=1;
int r=judge(x);
if(r==0)
{
print(x);
return 0;
}
else
{
if(!vis[r])
{
vis[r]=1;
q.push(x);
}
}
}
}
while(!q.empty())
{
x=q.front();
q.pop();
int i;
for(i=0;i<16;i++)
{
if(num[i])
{
x.base[x.len]=i;
x.len++;
int r=judge(x);
if(r==0)
{
print(x);
return 0;
}
else
{
if(!vis[r]&&x.len<499)
{
vis[r]=1;
q.push(x);
}
}
x.len--;
}
}
}
return -1;
}
int main()
{
int t;
scanf("%d",&t);
while(t--)
{
scanf("%d%d%d",&n,&c,&m);
int i;
memset(num,0,sizeof(num));
for(i=0;i='0'&&word[0]<='9')
num[word[0]-'0']=1;
else
num[word[0]-'A'+10]=1;
}
if(n!=0)
{
int ll=BFS();
if(ll==-1)
printf("give me the bomb please
");
}
else
{
if(num[0])
printf("0
");
else
printf("give me the bomb please
");
}
}
return 0;
}