圈乘运算问题

圈乘运算问题

时间: 1ms        内存:64M

描述:

关于整数的2 元圈乘运算⊙定义为(X⊙Y)=10进制整数X 的各位数字之和*10进制整数Y 的最大数字+Y 的最小数字。

例如,(9⊙30)=9*3+0=27。

对于给定的10进制整数X和K,由X 和⊙运算可以组成各种不同的表达式。试设计一个算法,计算出由X 和⊙运算组成的值为K 的表达式最少需用多少个⊙运算。

给定10 进制整数X 和K (1≤X,K≤1020) 。计算由X和⊙运算组成的值为K 的表达式最少需用多少个⊙运算。

输入:

输入数据有若干组,每组占一行,有2个10 进制整数X和K,中间以空格分开,输入以0 0结束。

输出:

对于每组数据,输出一个整数占一行,表示找到的最少⊙运算个数。如果无解,请输出“No answer”。

示例输入:

3 12
0 0

示例输出:

1

提示:

参考答案(内存最优[14248]):

import java.io.*;
import java.util.*;
import java.text.*;
import java.math.*;


public class Main {
	
	public static final int MAXN = 505;
	public static final int MAXM = 5005;
	public static final int MOD = 10000;
	public static final int INF = 1000000000;
	public static final double EPS = 1E-6;
	
	int kk, len, biglen, sum;
	int[] a = new int[3];
	int[] leftn;
	int[][] rightn;
	String s1, s2;
	
	void init() {
		biglen *= 9;
		rightn = new int[10][10];
		for (int i = 0; i < 10; i++) 
			for (int j = 0; j < 10; j++) 
				rightn[i][j] = Integer.MAX_VALUE;
		leftn = new int[biglen + 1];
		for (int i = 1; i <= biglen; i++) leftn[i] = Integer.MAX_VALUE;
		a[0] = Integer.MAX_VALUE; a[1] = a[2] = leftn[0] = 0;
		for (int i = 0; i < len; i++) 
			count(ctoi(s1.charAt(i)), a);
		rightn[a[0]][a[1]] = 0; sum = a[2];
		if (sum <= biglen) leftn[sum] = 0;
	}
	
	int ctoi(char x) {
		return (int)x - 48;
	}
	
	void count(int i, int[] a) {
		if (i < a[0]) a[0] = i;
		if (i > a[1]) a[1] = i;
		a[2] += i;
	}
	
	void trans(int t, int[] a) {
		a[0] = Integer.MAX_VALUE;
		while (t > 0) {
			int j = t % 10;
			t /= 10;
			count(j, a);
		}
	}
	
	void out(int x) { 
		if (x >= 0) System.out.println(x);
		else System.out.println("No answer");
	}
	
	int input() {
		s1 = cin.next();
		s2 = cin.next();
		if (s1.equals("0") && s2.equals("0")) {
			return -1;
		}
		if (s1.equals(s2)) {
			out(0);
			return 0;
		}
		len = s1.length();
		int big = 81 * len + 9;
		if (big < 171) big = 171;
		biglen = (int) Math.ceil(Math.log(big + 1.0) / Math.log(10.0));
		if (s2.length() > biglen) {
			out(-1);
			return 0;
		}
		kk = Integer.parseInt(s2, 10);
		if (kk > big) {
			out(-1);
			return 0;
		}
		return 1;
	}
	
	void compute() {
		int best = Integer.MAX_VALUE;
		boolean flag = true;
		while (flag) {
			flag = false;
			for (int i = 0; i <= biglen; i++) {
				if (leftn[i] < Integer.MAX_VALUE) {
					for (int j = 0; j < 10; j++) {
						for (int k = 0; k <= j; k++) {
							if (rightn[k][j] < Integer.MAX_VALUE) {
								int num = i > 0 ? i * j + k : sum * j + k;
								a[0] = Integer.MAX_VALUE; a[1] = a[2] = 0;
								trans(num, a);
								int cur = leftn[i] + rightn[k][j] + 1;
								if (cur < leftn[a[2]]) {
									leftn[a[2]] = cur;
									flag = true;
								}
								if (cur < rightn[a[0]][a[1]]) {
									rightn[a[0]][a[1]] = cur;
									flag = true;
								}
								if (num == kk && cur < best) {
									best = cur;
									flag = true;
								}
							}
						}
					}
				}
			}
		}
		if (best < Integer.MAX_VALUE) out(best);
		else out(-1);
	}
	
	void run() {
		int Case;
		while (true) {
			Case = input();
			if (Case < 0) return;
			if (Case < 1) continue;
			init();
			compute();
		}
	}
	
	public static void main(String[] args) {
		Main solved = new Main();
		solved.run();
	}
	
	Scanner cin = new Scanner(new BufferedInputStream(System.in));
}

参考答案(时间最优[324]):

import java.io.*;
import java.util.*;
import java.text.*;
import java.math.*;


public class Main {
	
	public static final int MAXN = 505;
	public static final int MAXM = 5005;
	public static final int MOD = 10000;
	public static final int INF = 1000000000;
	public static final double EPS = 1E-6;
	
	int kk, len, biglen, sum;
	int[] a = new int[3];
	int[] leftn;
	int[][] rightn;
	String s1, s2;
	
	void init() {
		biglen *= 9;
		rightn = new int[10][10];
		for (int i = 0; i < 10; i++) 
			for (int j = 0; j < 10; j++) 
				rightn[i][j] = Integer.MAX_VALUE;
		leftn = new int[biglen + 1];
		for (int i = 1; i <= biglen; i++) leftn[i] = Integer.MAX_VALUE;
		a[0] = Integer.MAX_VALUE; a[1] = a[2] = leftn[0] = 0;
		for (int i = 0; i < len; i++) 
			count(ctoi(s1.charAt(i)), a);
		rightn[a[0]][a[1]] = 0; sum = a[2];
		if (sum <= biglen) leftn[sum] = 0;
	}
	
	int ctoi(char x) {
		return (int)x - 48;
	}
	
	void count(int i, int[] a) {
		if (i < a[0]) a[0] = i;
		if (i > a[1]) a[1] = i;
		a[2] += i;
	}
	
	void trans(int t, int[] a) {
		a[0] = Integer.MAX_VALUE;
		while (t > 0) {
			int j = t % 10;
			t /= 10;
			count(j, a);
		}
	}
	
	void out(int x) { 
		if (x >= 0) System.out.println(x);
		else System.out.println("No answer");
	}
	
	int input() {
		s1 = cin.next();
		s2 = cin.next();
		if (s1.equals("0") && s2.equals("0")) {
			return -1;
		}
		if (s1.equals(s2)) {
			out(0);
			return 0;
		}
		len = s1.length();
		int big = 81 * len + 9;
		if (big < 171) big = 171;
		biglen = (int) Math.ceil(Math.log(big + 1.0) / Math.log(10.0));
		if (s2.length() > biglen) {
			out(-1);
			return 0;
		}
		kk = Integer.parseInt(s2, 10);
		if (kk > big) {
			out(-1);
			return 0;
		}
		return 1;
	}
	
	void compute() {
		int best = Integer.MAX_VALUE;
		boolean flag = true;
		while (flag) {
			flag = false;
			for (int i = 0; i <= biglen; i++) {
				if (leftn[i] < Integer.MAX_VALUE) {
					for (int j = 0; j < 10; j++) {
						for (int k = 0; k <= j; k++) {
							if (rightn[k][j] < Integer.MAX_VALUE) {
								int num = i > 0 ? i * j + k : sum * j + k;
								a[0] = Integer.MAX_VALUE; a[1] = a[2] = 0;
								trans(num, a);
								int cur = leftn[i] + rightn[k][j] + 1;
								if (cur < leftn[a[2]]) {
									leftn[a[2]] = cur;
									flag = true;
								}
								if (cur < rightn[a[0]][a[1]]) {
									rightn[a[0]][a[1]] = cur;
									flag = true;
								}
								if (num == kk && cur < best) {
									best = cur;
									flag = true;
								}
							}
						}
					}
				}
			}
		}
		if (best < Integer.MAX_VALUE) out(best);
		else out(-1);
	}
	
	void run() {
		int Case;
		while (true) {
			Case = input();
			if (Case < 0) return;
			if (Case < 1) continue;
			init();
			compute();
		}
	}
	
	public static void main(String[] args) {
		Main solved = new Main();
		solved.run();
	}
	
	Scanner cin = new Scanner(new BufferedInputStream(System.in));
}

题目和答案均来自于互联网,仅供参考,如有问题请联系管理员修改或删除。

点赞

发表评论

电子邮件地址不会被公开。必填项已用 * 标注