1010. Radix (25)

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

=================================================================
貌似是浙大PAT通过率最低的一题，6%
一开始很不解，为啥通过率这么低，明明是很容易读和做的一题，而且内存、时间都挺宽裕。
做起来才发现，对于我来说有这些问题：
1）思维定势。一开始误以为只可能进制到36为止，因为题目输入的一个数的进制最高只能到36，后来想想，这货是无穷无尽的，
假定A为已知进制为r1的数，B为待测进制(r2)的数，那么当第一次遇到r2, s.t. B@r2 > A@r1时，才是终止条件。
2）收敛速度。解决问题1后，竟然尼玛有一个运行超时了，仔细想想，r2按照线性递增测算的话，遇到以下输入将会是无穷无尽的时间才能判断
e.g.

zzzzzzzzzz 1 1 36

所以r2肯定不能一个一个来。
然后写了个简单的回溯，弄了个加速度的东西accRate，具体见代码》。如果一路成功会越走越快，如果遇到失败，那么退回backup的值，然后加速度回到1，然后继续。粗略一算这货的收敛速度或许是log级别的，直接放到pat判题，然后全过了:)
另外，发现c++用里面的pow算乘方其实挺快的，本来以为速度慢在这里，呵呵。
还有使用long long是因为按照题目的限定来说，最大的数 zzzzzzzzzz 放在一个long里面似乎不够用…当然用double或许可以，不过…浮点运算对cpu来说是个恐怖的事情吧
=================================================================
以下是
我的参考答案，肯定不是最好的
里面有些不必要的东西，懒得删了。
：

#include 
#include 
#include 
#include 
using namespace std;
char *N1, *N2;
long tag, radix;
long valueOfChar(char c)
{
	//get the value of a char
	//0~9,a-z
	long iC = (long)c;
	if(iC >= 0x30 && iC <= 0x39)
		return iC - 0x30;
	else if(iC >=0x61 && iC <= 0x7a) //a-z
		return iC - 0x57;
	else //wrong input
	{
		cerr << "??? " << c < 1
		int X = valueOfChar(input[0]);
		long long Z = X * pow(radix, size-1);
		return Z + getDecVal(input+1, radix, size-1);
	}
}
long getMinPossibleRadix(char* input)
{
	//获得最小可能的基数
	long maxDigit = 0;
	long nowDigit;
	while( (*input) != '')
	{
		nowDigit = valueOfChar((*input));
		if(nowDigit > maxDigit)
			maxDigit = nowDigit;
		input ++;
	}
	return maxDigit + 1;
}
char *trial;
int main()
{
	clock_t start,mid;
	N1 = new char[10];
	N2 = new char[10];
	long minPossibleRadix;
	cin >> N1 >> N2 >> tag >> radix;
	start = clock();
	long long lDecVal;
	if( tag == 1)
	{
		lDecVal = getDecVal(N1,radix);
		minPossibleRadix = getMinPossibleRadix(N2);
		trial = N2;
	}
	else
	{
		lDecVal = getDecVal(N2,radix);
		minPossibleRadix = getMinPossibleRadix(N1);
		trial = N1;
	}
	long long rVal = -1;
	int strSize = strlen(trial);
	long long accRate = 1;//加速度
	long long i= minPossibleRadix;
	long long backup = i;
	bool inTrial = false; //正在尝试的状态
	while(true)
	{
		rVal = getDecVal(trial,i,strSize);
		if(rVal == lDecVal)
		{
			cout << i;
			//mid = clock();
			//cout << mid - start << endl;
			return 0;
		}
		else if(rVal > lDecVal)
		{
			if(!inTrial)
				break;
			else
			{
				//回溯
				inTrial = false;
				if( i == backup + 1)
					break;
				i = backup;
				accRate = 1;
			}
		}
		else
		{
			inTrial = true;
			backup = i;
			i += accRate;
			accRate *= 10;
			//cout << i << endl;
		}
	}
	mid = clock();
	//cout << mid - start << endl;
	cout << "Impossible";
	return 0;
}