PAT-A1010 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
题目大意
题目给出两个数,其中一个的进制已知,求另一个数字的进制使两数大小相等;如该进制不存在,则输出“Impossible”。
解题思路
- 以字符串形式读取两个数字;
- 根据Tag及Radix求得其中一个十进制数num(注意:num和需求得的进制都要用long long类型,因为它们的取值可能会很大);
- 取目标进制值下限为最大字符代表的十进制数+1,令其为min;目标进制上限为min+1或num+1(取大值);
- 通过二分法求得结果,并在过程中剪枝以节约时间;
- 输出结果并返回0值。
代码
#include<stdio.h>
#define MAXN 15
int ChartoInt(char ch){
if(ch>='0'&&ch<='9'){
return ch-'0';
}else if(ch>='a'&&ch<='z'){
return ch-'a'+10;
}else{
return -1;
}
}
long long ChartoNum(char ch[],long long radix){
int i=0;
long long res=0;
while(ch[i]!='\0'){
res=radix*res+ChartoInt(ch[i]);
i++;
}
return res;
}
int FindMin(char a[]){
int i=0,min=0;
while(a[i]!=0){
if(ChartoInt(a[i])>min){
min=ChartoInt(a[i]);
}
i++;
}
return min+1;
}
int Compare(long long num,char a[],long long radix){
long long sum=0;
int i=0;
while(a[i]!='\0'){
sum=sum*radix+ChartoInt(a[i]);
if(sum>num){
return 1;
}
i++;
}
if(sum>num){
return 1;
}else if(sum<num){
return -1;
}else{
return 0;
}
}
int main(){
char a1[MAXN],a2[MAXN];
int tag,temp;
long long radix,num;
int i=0;
long long min,max,mid;
scanf("%s %s ",a1,a2);
scanf("%d%lld",&tag,&radix);
if(tag==1){
num=ChartoNum(a1,radix);
min=(long long)FindMin(a2);
max=(num>min?num+1:min+1);
while(min<max){
mid=(min+max)/2;
temp=Compare(num,a2,mid);
if(temp==1){
max=mid;
}else if(temp==-1){
min=mid;
}else{
printf("%d\n",mid);
return 0;
}
}
}else{
num=ChartoNum(a2,radix);
min=(long long)FindMin(a1);
max=(num>min?num+1:min+1);
while(min<max){
mid=(min+max)/2;
temp=Compare(num,a1,mid);
if(temp==1){
max=mid;
}else if(temp==-1){
min=mid;
}else{
printf("%d\n",mid);
return 0;
}
}
}
printf("Impossible\n");
return 0;
}
运行结果