Remainder
Description
Coco is a clever boy, who is good at mathematics. However, he is puzzled by a difficult mathematics problem. The problem is: Given three integers N, K and M, N may adds (‘+’) M, subtract (‘-‘) M, multiples (‘*’) M or modulus (‘%’) M (The definition of ‘%’ is given below), and the result will be restored in N. Continue the process above, can you make a situation that “[(the initial value of N) + 1] % K” is equal to “(the current value of N) % K”? If you can, find the minimum steps and what you should do in each step. Please help poor Coco to solve this problem.
You should know that if a = b * q + r (q > 0 and 0 <= r < q), then we have a % q = r.
Input
There are multiple cases. Each case contains three integers N, K and M (-1000 <= N <= 1000, 1 < K <= 1000, 0 < M <= 1000) in a single line.
The input is terminated with three 0s. This test case is not to be processed.
Output
For each case, if there is no solution, just print 0. Otherwise, on the first line of the output print the minimum number of steps to make “[(the initial value of N) + 1] % K” is equal to “(the final value of N) % K”. The second line print the operations to do in each step, which consist of ‘+’, ‘-‘, ‘*’ and ‘%’. If there are more than one solution, print the minimum one. (Here we define ‘+’ < ‘-‘ < ‘*’ < ‘%’. And if A = a1a2…ak and B = b1b2…bk are both solutions, we say A < B, if and only if there exists a P such that for i = 1, …, P-1, ai = bi, and for i = P, ai < bi)
Sample Input
2 2 2 -1 12 10 0 0 0
Sample Output
0 2 *+
我的代码
傻了这一题的%分号能直接处理掉，我愣了半天都没发现。最后从网上看的解法。
没有%的情况可以直接宽搜，并且%k之后设置标记位；如果有%的情况，一共就两种：一是%有且仅在第一个，二是%有且仅在第二个，并且第一个符号是*。
有%号的情况是这样分析的：无论出现多少个%，它的结果一定等于上述的两种，又要求的是最短的长度，所以有一个%的结果一定比有多个的更优。其中，如果一个%前面只有+和-时，使用%相当于把+和-的结果都还原后%m，所以无论使用多少个%，结果都和在一开始%m的一样；如果%前面有*，那么结果就为0。
所以只需要宽搜上面的三种情况就行了。
另外%的定义不是C中的定义，而是采用了数论中的方式，计算时相当于(now%k+k)%k。
#include<stdio.h>
#include<stack>
#include<string.h>
#include<vector>
using namespace std;
struct node{
int now,pre,step;
char ope;
node(){
}
node(int now,int pre,int step,char ope):now(now),pre(pre),step(step),ope(ope){
}
};
const char opes[6]={'0','+','-','*','%'};
int n,k,m,length,head;
int flag[1001];
vector<char> trail;
stack<char> s;
vector<node> v;
node temp;
int solve(int now,int o){
switch (o){
case '+':
return ((now+m)%k+k)%k;
case '-':
return ((now-m)%k+k)%k;
case '*':
return ((now*m)%k+k)%k;
default :
return 0;
}
}
void traceback(){
trail.clear();
while (!s.empty()){
s.pop();
}
node temp=v[v.size()-1];
while (temp.pre!=-1){
s.push(temp.ope);
temp=v[temp.pre];
}
while (!s.empty()){
trail.push_back(s.top());
s.pop();
}
}
void bfs(){
int done=0,res;
while(head<v.size()&&done==0){
temp=v[head++];
for (int i=1;i<=3;i++){
res=solve(temp.now,opes[i]);
if (flag[res]==0){
flag[res]=1;
v.push_back(node(res,head-1,temp.step+1,opes[i]));
if (res==((n+1)%k+k)%k){
if (temp.step+1<length){
length=temp.step+1;
traceback();
}
done=1;
break;
}
}
}
}
}
int main()
{
while(scanf("%d%d%d",&n,&k,&m)==3&&m!=0){
length=10000;
//无%
memset(flag,0,sizeof(flag));
head=0;
v.clear();
v.push_back(node((n%k+k)%k,-1,0,opes[0]));
flag[(n%k+k)%k]=1;
bfs();
//第一个是％
memset(flag,0,sizeof(flag));
head=1;
v.clear();
v.push_back(node((n%k+k)%k,-1,0,opes[0]));
v.push_back(node(((n%m+m)%m)%k,0,1,opes[4]));
flag[(n%k+k)%k]=1;
flag[((n%m+m)%m)%k]=1;
bfs();
//前两个是＊％
memset(flag,0,sizeof(flag));
head=2;
v.clear();
v.push_back(node((n%k+k)%k,-1,0,opes[0]));
v.push_back(node(((n*m)%k+k)%k,0,1,opes[3]));
v.push_back(node(0,1,2,opes[4]));
flag[(n%k+k)%k]=1;
flag[0]=1;
flag[((n*m)%k+k)%k]=1;
bfs();
if (length<10000){
printf("%d\n",length);
for (int i=0;i<trail.size();i++){
printf("%c",trail[i]);
}
}else{
printf("0");
}
printf("\n");
}
return 0;
}