# PAT (Advanced) 1010 (binary search + arbitrary decimal)

I thought it was a water problem and involved in the conversion of base system, so I wanted to be lazy and use java to do it. As a result, GG got involved. After thinking about it for a long time, I felt that the base limit should not be 36 before I started to change it.

The idea is to find the base upper and lower bounds of the search target. The lower bound is the largest character + 1 in the string. There are two situations in the upper bound: one is that if the decimal system is greater than the lower bound, the upper bound is the decimal number + 1; otherwise, the lower bound is 36.

There is also a pit that there may be more than one answer, two points to find the smallest answer.

```import java.math.BigDecimal;
import java.math.BigInteger;
import java.util.*;

public class Main{
static Scanner sc = new Scanner(System.in);
static String s1, s2;

static long findX(String s) {
char maxc = '0';
for(int i = 0; i < s.length(); i++) {
if(s.charAt(i) > maxc)
maxc = s.charAt(i);
}
if(maxc == '0') return 2;
if(maxc >= '1' && maxc <= '9') return maxc - 47;
else return maxc - 86;
}

static long exchange(String s, long rad) {
int len = s.length();
long sum = 0;
for(int i = 0; i < len; i++) {
if(s.charAt(i) <= '9')
sum = sum * rad +(s.charAt(i) - '0');
else
sum = sum * rad +(s.charAt(i) - 'a' + 10);
}
return sum;
}

static void solve(String s, long left, long right, long res) {
long mid = (right + left) / 2;
long ans = 0;
while(left <= right) {
long tmp = exchange(s, mid);
if(tmp > res || tmp < 0) {
right = mid - 1;
}
else if(tmp < res) {
left = mid + 1;
}
else {
ans = mid;
right = mid - 1;
}
mid = (left + right) / 2;
}
if(ans == 0)
System.out.println("Impossible");
else
System.out.println(ans);
}
public static void main(String[] args) {
s1 = sc.next(); s2 = sc.next(); tag = sc.nextInt(); rad = sc.nextInt();
long res, left;
String s;
if(tag == 1) {
left = findX(s2);
s = s2;
}
else {
left = findX(s1);
s = s1;
}
if(left >= res)
solve(s,left,36,res);
else
solve(s,left,res+1,res);

}
}

```

Tags: Java

Posted on Fri, 10 Jan 2020 08:46:18 -0800 by sdat1333