題目內(nèi)容

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???and ?, 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:

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:

Sample Output 1:

Sample Input 2:

Sample Output 2:

題目要點

本題 25 分，測試點共 20 個，為防止超時必須使用二分查找法，且需要考慮邊界情況，難度較大，下面給出一種解題思路。

tag的作用是指明N1或N2哪個數(shù)的進制已知，因此tag=1或tag=2是同一個問題，可以用條件語句分支討論或者以tag=1為準(zhǔn)，當(dāng)tag=2時交換N1和N2。這里我們分析時認(rèn)為tag=1。

由于這道題比較復(fù)雜，所以進制轉(zhuǎn)換的功能要封裝成函數(shù)便于復(fù)用。實現(xiàn)任意進制到10進制的轉(zhuǎn)換不難，如果使用ASCII碼轉(zhuǎn)換字符對應(yīng)的數(shù)值時，注意數(shù)字、字母在ASCII不是連續(xù)存儲的，需要判斷一下。本文在 Python 中是使用index方法，從0~z的字符串中找到字符對應(yīng)的下標(biāo)位置，即為對應(yīng)的數(shù)值。再用map函數(shù)得到各位對應(yīng)值的迭代器，通過列表生成器和sum函數(shù)求出最后的十進制值，代碼簡潔清晰。

二分查找法是針對有序序列的，這道題之所以可以使用二分查找是因為N2固定，隨著radix的增加，N2所對應(yīng)的十進制數(shù)值也就越大，構(gòu)成一個遞增序列。二分查找法需要的4個輸入量：有序序列、目標(biāo)值、low、high。目標(biāo)值是N1對應(yīng)的十進制值，而low和high是這道題的難點，在易錯分析中有詳細(xì)分析。經(jīng)過幾輪查找后查找到與目標(biāo)值相同的值時，當(dāng)前指針位置也就是相應(yīng)的radix，輸出mid，即為最終結(jié)果；如果查找失敗，那么輸出-1，在程序入口函數(shù)中判斷，輸出Impossible。

易錯分析

本題題設(shè)中沒有給出一個具體的數(shù)值范圍，因此 C/C++ 編寫時要采用long long形整數(shù)。Python 的整數(shù)長度足夠長，不用考慮這類問題。

對于下界low的確定，需要考慮輸入的任意進制數(shù)值。比如對于2進制數(shù)，各個位上不可能出現(xiàn)2，對于10進制數(shù)，各個位上不可能出現(xiàn)10，而是進位，從0重新開始。因此找出輸入的任意進制數(shù)值中最大的一位，再加1，即為low。比如，輸入105a，最大的是a，對應(yīng)的值是10，那么這個數(shù)至少是個10+1=11進制數(shù)。（測試點0）

對于上界high的確定，與下界類似。首先要考慮最大的可能性，即可能是N1所對應(yīng)的進制。然后，要考慮特殊的值，比如N1=0時，其上界不可能為0，至少是2，或者說high至少不能比low小，否則循環(huán)直接跳出。因此上界要取二者最大值，即high=max(N1_dec, low)。（測試點19）

Python 的數(shù)據(jù)類型是動態(tài)的，因此二分法計算中間元素的指針mid時必須將最終結(jié)果取整，否則會得到一個小數(shù)值，以此為radix計算輸入數(shù)的十進制時會得到錯誤結(jié)果。

源代碼