浙江财经大学
信息管理与工程学院

HDU 1104 Remainder(BFS)

本文由 Ocrosoft 于 2016-07-09 11:42:11 发表

Remainder

Time Limit: 6000/3000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 3784    Accepted Submission(s): 907

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
	
2 2 2 -1 12 10 0 0 0
 

Sample Output
	
0 2 *+
 

Solution

题意:给出n,k,m,对n进行+k,-k,*k,%k的操作,能不能使(n+1)%k==n%k,前一个n使原来的n,后一个使操作过后的n。

数论完全不会,自己瞎搞RE了…

#include <cstdio>
#include <cstdlib>
#include <iostream>
#include <conio.h>
#include <cmath>
#include <algorithm>
#include <list>
#include <stack>
#include <string>
#include <vector>
#include <cstring>
#include <cctype>
#include <queue>
#include <set>
#include <climits>
#define ms(a) memset(a,0,sizeof(a))
using namespace std;
template <typename T>
T read(T& t)
{
    cin>>t;
    return t;
}
int n,k,m,km;
int vis[1000010];
struct S
{
    S()
    {
        n=0,step=0,ans.clear();
    }
    S(int m)
    {
        n=m,step=0,ans.clear();
    }
    int n,step;
    string ans;
};
bool bfs()
{
    ms(vis);
    queue<S> q;
    q.push(S(n));
    S t,tt;
    vis[(n%k+k)%k]=1;
    while(!q.empty())
    {
        t=q.front();
        q.pop();
        if(((n+1)%k+k)%k==((t.n%k)+k)%k)
        {
            printf("%d\n",t.ans.size());
            cout<<t.ans<<endl;
            return 1;
        }
        //+
        tt=t;
        tt.n=(tt.n+m)%km;
        tt.ans.push_back('+');
        if(!vis[(tt.n%k+k)%k])
        {
            vis[(tt.n%k+k)%k]=1;
            q.push(tt);
        }
        //-
        tt=t;
        tt.n=(tt.n-m)%km;
        tt.ans.push_back('-');
        if(!vis[(tt.n%k+k)%k])
        {
            vis[(tt.n%k+k)%k]=1;
            q.push(tt);
        }
        //*
        tt=t;
        tt.n=(tt.n*m)%km;
        tt.ans.push_back('*');
        if(!vis[(tt.n%k+k)%k])
        {
            vis[(tt.n%k+k)%k]=1;
            q.push(tt);
        }
        //%
        tt=t;
        tt.n=(tt.n%m+m)%m;
        tt.ans.push_back('%');
        if(!vis[(tt.n%k+k)%k])
        {
            vis[(tt.n%k+k)%k]=1;
            q.push(tt);
        }
    }
    return 0;
}
int main()
{
    while(cin>>n>>k>>m&&(n||k||m))
    {
        km=k*m;
        if(!bfs())printf("0\n");
    }
    return 0;
}

 

欢迎分享与转载,请保留链接与出处。Ocrosoft » HDU 1104 Remainder(BFS)

点赞 (0)or拍砖 (0)

评论 抢沙发

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址