首页 > ACM题库 > HDU-杭电 > HDU 1104 Remainder-BFS-[解题报告] java
2013
11-27

HDU 1104 Remainder-BFS-[解题报告] java

Remainder

问题描述 :

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.

输入:

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.

输出:

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)

样例输入:

2 2 2
-1 12 10
0 0 0

样例输出:

0
2
*+

本身只是BFS搜索,需要注意的有几点:

1. 题目中的modulus操作与计算机的%不同。modulus(a,b) = (a%b+b)%b。 即保证结果一定为正。而计算机中是先abs(a)%b,再把a符号付给它。

2. 在搜索过程中值会越来越大,不便于存入hash数组,由于计算的值总是用于比较modulus(tmp, K)==modulus(N+1,K),因此我们可以不必保存tmp,而直接对tmp取modulus。

3. 由于存在modulus(tmp, M)的OP,因此要保证tmp一直还与M线性同余。取tmp = modulus(tmp,KM),这样既可以保证tmp比较小,又保证与K,M都线性同余,使得之后的modulus(tmp,K)和modulus(tmp,M) 效果都与不对tmp进行任何处理效果相同。

4.注意Node中存的和hash的都是经过处理的tmp值。每次检查是否得到正确结果,需要检查 modulus(经过处理的tmp,K)==modulus(N+1,K)

import java.util.*;

public class Main {
	String ops = "+-*%";
	class Node {
		int n;
		String path;
	}
	int N, K, M, result, KM;
	Scanner input = new Scanner(System.in);
	LinkedList<Node> list = new LinkedList<Node>();
	boolean[] hash = new boolean[1000001];

	public static void main(String[] args) {
		new Main().work();
	}

	public int modulus(int a, int b) {
		return (a % b + b) % b;
	}

	public void work() {
		while (input.hasNext()) {
			N = input.nextInt();
			K = input.nextInt();
			M = input.nextInt();
			if (N == 0 && K == 0 && M == 0) {
				break;
			}
			KM = K * M;
			list.clear();
			Arrays.fill(hash, false);
			Node head = new Node();
			head.path = "";
			head.n = N;
			hash[modulus(N, KM)] = true;
			result = modulus(N + 1, K);
			list.add(head);
			bfs();
		}
		input.close();
	}

	public void bfs() {
		while (!list.isEmpty()) {
			Node node = list.poll();
			if (modulus(node.n, K) == result) {
				System.out.println(node.path.length());
				System.out.println(node.path);
				return;
			}
			for (int i = 0; i < ops.length(); i++) {
				doOp(ops.charAt(i), node);
			}
		}
		System.out.println(0);
	}

	public void doOp(char op, Node node) {
		int tmp = 0;
		switch (op) {
		case '+':
			tmp = modulus(node.n + M, KM);
			break;
		case '-':
			tmp = modulus(node.n - M, KM);
			break;
		case '*':
			tmp = modulus(node.n * M, KM);
			break;
		case '%':
			tmp = modulus(modulus(node.n, M), KM);
			break;
		}
		if (!hash[tmp]) {
			hash[tmp] = true;
			Node newNode = new Node();
			newNode.path = node.path + op;
			newNode.n = tmp;
			list.addLast(newNode);
		}
	}
}


  1. 可以参考算法导论中的时间戳。就是结束访问时间,最后结束的顶点肯定是入度为0的顶点,因为DFS要回溯