Pat1010代码
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 10Sample Output 1:
2Sample Input 2:
1 ab 1 2Sample Output 2:
Impossible
#include<cstdio>
#include<cstring>
#define MAX 11using namespace std;int IsEqual(char *N1,char *N2)//根据两个字符串的情况分类讨论
{int i,len1,len2;len1=strlen(N1);len2=strlen(N2);if(len1==1&&len2==1&&N1[0]==N2[0])//两个字符相等，如7 7 1 10，基数应为8return 0;else if(len1==len2&&len2>1){for(i=0;i<len1;i++)if(N1[i]!=N2[i])return 2;//两字符串不相同，搜索结果return 1;//两个字符串相同，且长度不为1，则基数与另一个基数相同} //eg:22 22 1 40则基数也应为40elsereturn 2;//两个字符串不同，进行搜索
}long long ChangeToInt(char str[],int base)//转换成整型
{long long n=0;for(int i=0;str[i]!='\0';i++){if(str[i]>='0'&&str[i]<='9')n=n*base+str[i]-'0';else if(str[i]>='a'&&str[i]<='z')n=n*base+str[i]-'a'+10;}return n;
}long long FindSmallBase(char str[])
{long long i,max,base;max=0;for(i=0;str[i]!='\0';i++)if(str[i]>max)max=str[i];if(max>='0'&&max<'9')base=max-'0'+1;else if(max=='9')base=10;elsebase=max-'a'+10+1;return base;
}int compare(char *N,long long radix,long long max)
{long long i,sum=0;for(i=0;N[i]!='\0';i++){if(N[i]>='0'&&N[i]<='9')sum=sum*radix+N[i]-'0';elsesum=sum*radix+N[i]-'a'+10;if(sum>max)return -1;//防止溢出，因为此时radix值偏大，应减小radix进行搜索} //没有必要再进行计算了，最后可能溢出if(sum>max)return -1;else if(sum<max)return 1;elsereturn 0;
}long long BinSearch(char *N,long long low,long long high,long long ans)
{int result;long long mid;while(low<=high){mid=low+(high-low)/2;result=compare(N,mid,ans);if(result==1)low=mid+1;else if(result==-1)high=mid-1;elsereturn mid;}return -1;
}int main(int argc,char *argv[])
{char N1[MAX],N2[MAX];int tag,radix,equal;long long n1,n2;long long base,ans,max;scanf("%s %s %d %d",N1,N2,&tag,&radix);equal=IsEqual(N1,N2);if(equal==0){if(N1[0]>='0'&&N1[0]<='9'){printf("%d\n",N1[0]-'0'+1);return 0;}else{printf("%d\n",N1[0]-'a'+11);return 0;}}else if(equal==1){printf("%d\n",radix);return 0;}else{if(tag==1){n1=ChangeToInt(N1,radix);base=FindSmallBase(N2);max=n1>base?n1:base;ans=BinSearch(N2,base,max,n1);if(ans==-1)printf("Impossible\n");elseprintf("%lld\n",ans);}else {n2=ChangeToInt(N2,radix);base=FindSmallBase(N1);max=n2>base?n2:base;//11 b 1 10之类的情况ans=BinSearch(N1,base,max,n2);if(ans==-1)printf("Impossible\n");elseprintf("%lld\n",ans);}}return 0;
}
