PAT-Advanced-1010 Radix

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可能会很大,N1和N2也可能达到很大,如果按我个人理解,十个字符都是 ‘a’ 那就是表示10个10排在一起,就是10^20,long long int 能表示的范围也才10^19,庆幸的是这个数的radix基本不会很大,一般情况下radix都不可能达到10^19这么大的数。

这题如果采用穷举法是很不现实的,基本上肯定是要超的,这里对条件进行解读:

1、如果N1>N2 , 在有解的条件下,用N2去表示N1 ,这时候N2的基数一定是大于N1的基数,但是不会大于N1这个数。

2、如果N1>N2,在有解的条件下,用N1去表示N2,这时候N1的基数一定是小于N2的基数。

反之亦然!注:N1、N2的比对是在十进制的条件下进行的,不需要进制转换。

问题

思路应该是没有问题,我也看了别人的代码,思路差不多,但是就是有1个测试点没有通过。解决:将最下界最大设置为:35就行,不知道为什么会超过35就不通过,暂时先放着。

 

此条目发表在算法与数据结构分类目录,贴了标签。将固定链接加入收藏夹。

发表评论

电子邮件地址不会被公开。 必填项已用*标注