原题目
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
andN2
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, anda
-z
represent the decimal numbers 10-35. The last number radix is theradix
ofN1
iftag
is 1, or ofN2
iftag
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, printImpossible
. 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
题目大意
给一对正整数,例如6和110,等式 6 = 110成立的条件是6是一个十进制数字且110是一个二进制数字。
输入一行4个正整数,N1和N2是两个不多于10个数字的数,其中一个数字从集合{0-9, a
-z
}中取且数值小于它的进制。输入的radix
表示第tag
个数的进制,tag
取1或2。输出未知进制数能满足等式 N1
= N2
时最小的进制,若不能满足等式则输出Impossible
。
题解
不愧是通过率只有0.11的题,实在是太多坑了。
首先10位的数字不能直接用int进行存储和读入。一开始我是自己写了大整数模板来进行数据存储及进制转换,但是因为太麻烦就放弃了懒得写除法。看过其他人写的题解后知道了用long long
可以直接过,但是也存在溢出的问题,在进行进制转换时如果long long
溢出为负需及时舍去。
然后就是题目中说的每一位数字都从{0-9, a
-z
}中取,即每一位数字的大小都不超过35,并不代表radix
最高只能取36,相反,进制的数值可以在long long
的范围内取,只要不超过已知进制数的十进制数值加1。
最后,如果选用暴力搜索的办法,从未知进制数的最大数字加1一直搜索到已知进制数的数值加1,在测试点7会直接超时用大整数做的时候直接内存超限了。因此只能选择二分法,选好上下界,迭代出结果。注意要求输出满足条件的最小进制不过好像不写那段代码也能过。
C语言代码如下:
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define max(a, b) (a) > (b) ? (a) : (b)
long long string_2_long(char *num, long long radix){
long long ret = 0;
long long base = 1;
for(int i = strlen(num) - 1;i >= 0;--i){
int time = num[i] > '9' ? num[i] - 'a' + 10 : num[i] - '0';
if(ret > ret + time * base) return -1;
ret += time * base;
base *= radix;
}
return ret;
}
int main(){
char num1[12], num2[12];
int tag;
long long radix;
char maxx = 0;
scanf("%s%s%d %lld", num1, num2, &tag, &radix);
long long src, dest;
if(tag == 1){
src = string_2_long(num1, radix);
memcpy(num1, num2, 12); //将num1作为待确定的字符串
}
else{
src = string_2_long(num2, radix);
}
for(int i = 0;i < strlen(num1);++i){
maxx = max(num1[i], maxx);
}
long long low = (maxx > '9' ? maxx - 'a' + 10 : maxx - '0') + 1;
long long high = max(src + 1, low);
if(src < string_2_long(num1, low)){
printf("Impossible\n");
return 0;
}
while(high >= low){
long long mid = (high + low) / 2;
long long tmp = string_2_long(num1, mid);
if(src == tmp){
mid--;
while (mid >= low){
if(string_2_long(num1, mid) == src){
mid--;
}
else{
break;
}
}
printf("%d\n", mid + 1);
return 0;
}
else if(src < tmp || tmp < 0){
high = mid - 1;
}
else{
low = mid + 1;
}
}
printf("Impossible\n");
return 0;
}