hdu 1104 Remander（BFS+数論）
タイトル:http://acm.hdu.edu.cn/showproblem.php?pid=1104
Remander
Time Limit：6000/3000 MS（Java/Others） メモリLimit：65536/32768 K（Java/Others）Total Submission（s）：3320 Acceepted Submission(s)：752
Problem Description
Coco is a clever boy，who is goodt at mathematic.However，he is puzled by a difficult mathematch probles.The probles:Gvent three integers N，K and M，N may adds('+')M，subtrator's(The problemi)m.'，The beduct.'，The bedemoduct.'s.'s.'s.'s.'s.'s.'and the result will be restored in N.Continue the process above，can you make a situation that"((the initial value of N)+1%"is equal to"(the current value of N)"K？If you can，find the minimum steps and what you shound do in each step.Please help poor Coco to solive this proble.
You shound know that if a=b*q+r(q>0 and 0==r
Input
The re are multiple cases.Each case contains three integers N，K and M(-1000<=N==1000,1The input is terminated with three 0 s.This test case is not to be processed.
Output
For each case，if there isのsolution，jusprint 0.Other wise，on the first line of the out print the minimum number of steps to make，[(the initial value of N)+1]]K"is equal to"‘＊’and‘%’.If there re re re more more more than one solution、print the minimumone.(Here we define'+''''-''''''''''''.And i i A=a 2...ak and B=b 1 b 1 b 2...bk arboth soutions、weef、weexsoutininin、weeex=we、weemimimimimimimitititi、we、we=======================、weeiiiiiiiiiife、we、weeeeeeeeeeeeeeeeee
Sample Input
Sample Output
Remander
Time Limit：6000/3000 MS（Java/Others） メモリLimit：65536/32768 K（Java/Others）Total Submission（s）：3320 Acceepted Submission(s)：752
Problem Description
Coco is a clever boy，who is goodt at mathematic.However，he is puzled by a difficult mathematch probles.The probles:Gvent three integers N，K and M，N may adds('+')M，subtrator's(The problemi)m.'，The beduct.'，The bedemoduct.'s.'s.'s.'s.'s.'s.'and the result will be restored in N.Continue the process above，can you make a situation that"((the initial value of N)+1%"is equal to"(the current value of N)"K？If you can，find the minimum steps and what you shound do in each step.Please help poor Coco to solive this proble.
You shound know that if a=b*q+r(q>0 and 0==r
Input
The re are multiple cases.Each case contains three integers N，K and M(-1000<=N==1000,1
Output
For each case，if there isのsolution，jusprint 0.Other wise，on the first line of the out print the minimum number of steps to make，[(the initial value of N)+1]]K"is equal to"‘＊’and‘%’.If there re re re more more more than one solution、print the minimumone.(Here we define'+''''-''''''''''''.And i i A=a 2...ak and B=b 1 b 1 b 2...bk arboth soutions、weef、weexsoutininin、weeex=we、weemimimimimimimitititi、we、we=======================、weeiiiiiiiiiife、we、weeeeeeeeeeeeeeeeee
Sample Input
2 2 2
-1 12 10
0 0 0
Sample Output
0
2
*+
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
const int md=1005;
int n,k,m,km;
bool vis[1000010];
struct node{
int val,step,top;
char path[1000];
void init(){
val=step=top=0;
memset(path,0,sizeof(path));
}
};
node que[md];
void bfs(){
int q1=0,q2=0;
node t;
t.init();
t.val=n;
que[q2++]=t;
vis[(t.val%k+k)%k]=1;
while(q1!=q2){
node cur=que[q1],temp;
q1=(q1+1)%md;
if(((n+1)%k+k)%k==(cur.val%k+k)%k){
printf("%d
%s
",cur.step,cur.path);
return ;
}
for(int i=0;i<4;i++){
temp.init();
strcpy(temp.path,cur.path);
temp.top=cur.top;
if(i==0){
temp.val=(cur.val+m)%km;
temp.path[temp.top++]='+';
}
else if(i==1){
temp.val=(cur.val-m+km)%km;
temp.path[temp.top++]='-';
}
else if(i==2){
temp.val=cur.val*m%km;
temp.path[temp.top++]='*';
}
else {
temp.val=(cur.val%m+m)%m%km;
temp.path[temp.top++]='%';
}
temp.step=cur.step+1;
if(!vis[(temp.val%k+k)%k]){
que[q2]=temp;
q2=(q2+1)%md;
vis[(temp.val%k+k)%k]=1;
}
}
}
printf("0
"); //
}
int main()
{
//freopen("cin.txt","r",stdin);
while(cin>>n>>k>>m){
if(n==0&&m==0&&k==0) break;
km=k*m;
memset(vis,0,sizeof(vis));
bfs();
}
return 0;
}