圈乘运算问题
时间： 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));
}题目和答案均来自于互联网，仅供参考，如有问题请联系管理员修改或删除。