# 圈乘运算问题

``````3 12
0 0``````

``1``

``````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);
}

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));
}``````

``````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);
}

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));
}``````