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 int tag, rad;
	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) {
			res = exchange(s1, rad);
			left = findX(s2);
			s = s2;
		}
		else {
			res = exchange(s2, rad);
			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