PAT 解题报告 1010. Radix: Binary Search以及Overflow检测

Overview

PAT 解题报告 1010. Radix: 所求的Target有可能是long long 都存不下的数字, AC的方法是使用Binary Search并且需要非常注意Overflow的特殊检测.

PAT 1010. Radix题目描述:

给你两个数字, 以及其中某一个数字的radix, 让你求出另一个数字的radix使得这两个数字在各自的radix下化成十进制下的相等的值. 如果不可能就输出impossible.

下面是英文原题:

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

算法分析:

这个题目绝对是坑死人不偿命!所求的radix有可能是连long long都存不下的一个数字. 假设已经知道那个数字基于给定radix的十进制等价值叫做target, 问题就是要求另个一给定的数字s(用string  s表示 因为不一定是数字)的可能radix, 使得s基于算出的radix的十进制等价值和target相等。 因为radix有可能很大很大, long long 也未必能存下, 一般可以AC的做法就是二分查找这个radix, 可以在1和max_long_long之间进行二分查找, 每次找到一个候选数字radix, 那么s基于这个radix有一个对应的十进制值, 把这个十进制值和target比较就能确定下一个查找的区间是前面一半后面一半(因为要二分), 但是注意这里的比较也很tricky, 非常容易overflow, 所以不能用一般的比较, 不能直接就去算s基于radix的对应十进制值, 而是需要专门写一点代码尽量预防overflow. (说尽量是因为数字真的大的话, 还是会overflow的). 下面的代码可以预防一部分可能的overflow, 因为如果s的值比target大的话, 有时候不需要完全展开s就可以知道比较的结果了.

//1  if target > s
//0  if target = s
//-1 if target < s int cmp(long long target, const string &s, long long radix) {     long long sv = 0;     long long multip = 1;     for(int i=s.size()-1; i>=0; i--) {
        sv += (match(s[i]) * multip); //match(s[i]) return the numerical value of thie character like A = 10
        if(sv > target) return -1;// avoid overflow
        multip *= radix;
    }
    if(sv > target)
        return -1;
    else if(sv == target)
        return 0;
    else
        return 1;
}

这样一步步比较之后然后二分区间,一直二分下去直到找到一个radix使得和target相等了, 就结束, 或者我们找不到这样的radix,就输出impossible 特别注意点:overflow!!!

Summary

PAT 解题报告 1010. Radix: 所求的Target有可能是long long 都存不下的数字, AC的方法是使用Binary Search并且需要非常注意Overflow的特殊检测.

 

Written on April 13, 2013