[Java] 1010. Radix (25)-PAT甲级

1010. Radix (25)
Given a pair of positive integers, for example, 6 and 110, can this equation 6 = 110 be true? The answer is “yes”, if 6 is a decimal number and 110 is a binary number.

Now for any pair of positive integers N1 and N2, your task is to find the radix of one number while that of the other is given.

Input Specification:

Each input file contains one test case. Each case occupies a line which contains 4 positive integers:
N1 N2 tag radix
Here N1 and N2 each has no more than 10 digits. A digit is less than its radix and is chosen from the set {0-9, a-z} where 0-9 represent the decimal numbers 0-9, and a-z represent the decimal numbers 10-35. The last number “radix” is the radix of N1 if “tag” is 1, or of N2 if “tag” is 2.

Output Specification:

For each test case, print in one line the radix of the other number so that the equation N1 = N2 is true. If the equation is impossible, print “Impossible”. If the solution is not unique, output the smallest possible radix.

Sample Input 1:
6 110 1 10
Sample Output 1:
2
Sample Input 2:
1 ab 1 2
Sample Output 2:
Impossible

PS：感谢github用户@fs19910227提供的pull request～

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.math.BigInteger;

public class Main {
    private static String binarySearch(final String value, final BigInteger expect) {
        //重点在于最大值和最小值的界定 下界大于 所有位中最大值 考虑2 2 1 10 这个case
        BigInteger start = BigInteger.valueOf(maxBitValue(value) + 1);
        //上界不小于下界,不大于expect 考虑200000 1 1 10 这个case
        BigInteger end = expect.compareTo(start) < 0 ? start : expect;

        BigInteger result_radix = null;
        while (end.compareTo(start) >= 0) {
            BigInteger middle = start.add(end).divide(BigInteger.valueOf(2));
            BigInteger ten_value = convert2ten(value, middle);
            int compare = ten_value.compareTo(expect);
            if (compare >= 0) {
                if (compare == 0 && (result_radix == null || middle.compareTo(result_radix) < 0)) {
                    result_radix = middle;
                }
                end = middle.subtract(BigInteger.valueOf(1));
            } else {
                start = middle.add(BigInteger.valueOf(1));
            }
        }
        return result_radix == null ? "Impossible" : result_radix + "";
    }

    private static BigInteger convert2ten(String value, BigInteger radix) {
        char[] chars = value.toCharArray();
        BigInteger sum = BigInteger.ZERO;
        for (char aChar : chars) {
            int v = char2int(aChar);
            if (radix.compareTo(BigInteger.valueOf(v)) < 0) {
                return BigInteger.valueOf(Long.MAX_VALUE);
            }
            sum = sum.multiply(radix).add(BigInteger.valueOf(v));
        }
        return sum;
    }

    private static int maxBitValue(String value) {
        int max = 0;
        for (char c : value.toCharArray()) {
            int i = char2int(c);
            if (i > max) max = i;
        }
        return max;
    }

    private static int char2int(char c) {
        int ret = c - 48;
        return ret < 10 ? ret : ret - 39;
    }

    public static void main(String[] args) throws IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        String[] split = reader.readLine().split(" ");
        String v1 = split[0], v2 = split[1];
        String know_v = v1, unknow_v = v2;
        BigInteger know_radix = BigInteger.valueOf(Integer.valueOf(split[3]));
        if ("2".equals(split[2])) {
            know_v = v2;
            unknow_v = v1;
        }
        //期望值转化为十进制 相当于把输入转化为 N1 N2 1 10
        BigInteger expect = convert2ten(know_v, know_radix);
        String s = binarySearch(unknow_v, expect);
        System.out.println(s);
    }
}

import java.io.BufferedReader;

import java.io.IOException;

import java.io.InputStreamReader;

import java.math.BigInteger;

public class Main {

private static String binarySearch(final String value, final BigInteger expect) {

//重点在于最大值和最小值的界定下界大于所有位中最大值考虑2 2 1 10 这个case

BigInteger start = BigInteger.valueOf(maxBitValue(value) + 1);

//上界不小于下界,不大于expect 考虑200000 1 1 10 这个case

BigInteger end = expect.compareTo(start) < 0 ? start : expect;

BigInteger result_radix = null;

while (end.compareTo(start) >= 0) {

BigInteger middle = start.add(end).divide(BigInteger.valueOf(2));

BigInteger ten_value = convert2ten(value, middle);

int compare = ten_value.compareTo(expect);

if (compare >= 0) {

if (compare == 0 && (result_radix == null || middle.compareTo(result_radix) < 0)) {

result_radix = middle;

}

end = middle.subtract(BigInteger.valueOf(1));

} else {

start = middle.add(BigInteger.valueOf(1));

}

return result_radix == null ? "Impossible" : result_radix + "";

}

private static BigInteger convert2ten(String value, BigInteger radix) {

char[] chars = value.toCharArray();

BigInteger sum = BigInteger.ZERO;

for (char aChar : chars) {

int v = char2int(aChar);

if (radix.compareTo(BigInteger.valueOf(v)) < 0) {

return BigInteger.valueOf(Long.MAX_VALUE);

}

sum = sum.multiply(radix).add(BigInteger.valueOf(v));

}

return sum;

}

private static int maxBitValue(String value) {

int max = 0;

for (char c : value.toCharArray()) {

int i = char2int(c);

if (i > max) max = i;

}

return max;

}

private static int char2int(char c) {

int ret = c - 48;

return ret < 10 ? ret : ret - 39;

}

public static void main(String[] args) throws IOException {

BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));

String[] split = reader.readLine().split(" ");

String v1 = split[0], v2 = split[1];

String know_v = v1, unknow_v = v2;

BigInteger know_radix = BigInteger.valueOf(Integer.valueOf(split[3]));

if ("2".equals(split[2])) {

know_v = v2;

unknow_v = v1;

}

//期望值转化为十进制相当于把输入转化为 N1 N2 1 10

BigInteger expect = convert2ten(know_v, know_radix);

String s = binarySearch(unknow_v, expect);

System.out.println(s);

}

❤ 点击这里 -> 订阅《PAT | 蓝桥 | LeetCode学习路径 & 刷题经验》by 柳婼

❤ 点击这里 -> 订阅《从放弃C语言到使用C++刷算法的简明教程》by 柳婼

❤ 点击这里 -> 订阅PAT甲级乙级、蓝桥杯、GPLT天梯赛、LeetCode题解离线版