2426.txt

北大ACM题目例程 详细的解答过程 程序实现 算法分析

# include <stdio.h>
# include <string.h>

# define MAX 1000010

int n,m,k,s,t,base;

int v[MAX],prev[MAX],step[MAX],qs,qe,q[MAX];
char op[MAX];

int bfs(void){
	int i,j;
	memset(v,0,sizeof(v));
	s = (n%base+base)%base;
	t = (s+1)%base;
	qs = qe =0;
	q[qe++] = s; v[s] = 1;
	prev[s] = -1; step[s]=0;
	while(qs<qe){
		i = q[qs++];
		if(i%k == t%k){
			t=i;
			return step[i];
		}
		if(!v[(i+m)%base]){
			j=(i+m)%base;
			q[qe++] = j;
			v[j] = 1;
			prev[j] = i;
			step[j] = 1+step[i];
			op[j] = '+';
		}
		if(!v[((i-m)%base+base)%base]){
			j=((i-m)%base+base)%base;
			q[qe++] = j;
			v[j] = 1;
			prev[j] = i;
			step[j] = 1+step[i];
			op[j] = '-';
		}
		if(!v[(i*m)%base]){
			j=(i*m)%base;
			q[qe++] = j;
			v[j] = 1;
			prev[j] = i;
			step[j] = 1+step[i];
			op[j] = '*';
		}
		if(!v[(i%m)]){
			j=(i%m);
			q[qe++] = j;
			v[j] = 1;
			prev[j] = i;
			step[j] = 1+step[i];
			op[j] = '%';
		}
	}
	return -1;
}

void out(void){
	char ans[MAX];
	int curr = t,cnt=0;
	while(prev[curr] != -1){
		ans[cnt++]= op[curr];
		curr = prev[curr];
	}
	while(cnt--)printf("%c",ans[cnt]);
	printf("\n");
}

int main(){
	while(scanf("%d%d%d",&n,&k,&m), k){
		base = k*m;
		int st = bfs();
		if(st == -1)printf("0\n");
		else {
			printf("%d\n",st);
			out();
		}
	}
	return 0;
}