hdoj1104 Remainder

发表于 | 分类于 ， | 阅读量 次

Problem 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

1
2
3
2 2 2
-1 12 10
0 0 0

Sample Output

1
2
3
0
2
*+

http://acm.hdu.edu.cn/showproblem.php?pid=1104

这题采用的是广搜和余数定理。

为了防止每次的数太大需要取模，但是因为有个’%m’的操作，每次取模的数可以定为km,还有就是定义一个vis[]数组来除重，最先出现的肯定是最优解，还有就是广搜时要按照’+’,’-‘,’*’,’%’的顺序（题目里要求）.

tmp.v=((cur.v+m)%km+km)%km这个是余数定理中经典的操作，为了保证结果是正的，因为平常中mod后的结果是正的，而计算机处理’%’时的结果符号不变。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
#include<iostream>
#include<cstdio>
#include<map>
#include<string>
#include<cstring>
#include<stack>
#include<queue>
using namespace std;
#define maxn 300000

struct Coke{
    int v;
    int t;
    string s;
};
int vis[maxn];

int main()
{
    int n,k,m;
    while(~scanf("%d%d%d",&n,&k,&m)&&!(!n&&!k&&!m))
    {
        memset(vis,0,sizeof(vis));
        int km=k*m;
        int flag=1;

        queue<Coke> q;

        Coke fir;
        fir.v=n;fir.t=0;fir.s="";
        q.push(fir);
        vis[(n%k+k)%k]=1;
        while(!q.empty())
        {
            Coke cur=q.front();

            q.pop();
            if(((n+1)%k+k)%k==(cur.v%k+k)%k) {cout<<cur.t<<endl;cout<<cur.s<<endl;flag=0;break;}

            Coke tmp;
            tmp.t=cur.t+1;
            for(int i=1;i<=4;i++)
            {
                if(i==1){tmp.v=((cur.v+m)%km+km)%km;tmp.s=cur.s+"+";}
                if(i==2){tmp.v=((cur.v-m)%km+km)%km;tmp.s=cur.s+"-";}
                if(i==3){tmp.v=((cur.v*m)%km+km)%km;tmp.s=cur.s+"*";}
                if(i==4){tmp.v=(cur.v%m+m)%m;tmp.s=cur.s+"%";}

                if(vis[(tmp.v%k+k)%k]==1) continue;
                vis[(tmp.v%k+k)%k]=1;
                q.push(tmp);

            }
        }
        if(flag)cout<<0<<endl;

    }
}