PAT 1010

1010. Radix (25)

时间限制
400 ms
内存限制
32000 kB
代码长度限制
16000 B
判题程序
Standard
作者
CHEN, Yue
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

题目网址: http://pat.zju.edu.cn/contests/pat-a-practise/1010

这题关键就是大数据的处理和二分法的查找。

用Python语言很容易就做出来了,因为基本不用考虑溢出的问题,需要用到二分查找,否则会有大数据超时。

Python代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
line = raw_input().split()
if line[2]=='1':
num1 = list(line[0])
num2 = list(line[1])
else:
num1 = list(line[1])
num2 = list(line[0])
radix1 = int(line[3]) # the radix of num1
decNum1 = 0
for num in num1:
decNum1 *= radix1
if '0'<=num<='9':
decNum1 += int(num)
else:
decNum1 += ord(num) - ord('a') + 10

num2_min = min(num2)
if '0'<=num2_min<='9':
radix2_min = int(num2_min) + 1
else:
radix2_min = ord(num2_min) - ord('a') + 10 + 1

radix2_max = decNum1 + 1

while radix2_max >= radix2_min:
decNum2 = 0
radix2 = (radix2_max + radix2_min)/2
for num in num2:
decNum2 *= radix2
if '0'<=num<='9':
decNum2 += int(num)
else:
decNum2 += ord(num) - ord('a') + 10
if decNum2 > decNum1:
radix2_max = radix2 - 1
elif decNum2 < decNum1:
radix2_min = radix2 + 1
else:
print radix2
break
else: print "Impossible"

用C语言就没那么容易了,用64位的long long来表示数据,但是还是存在溢出的危险,于是需要对溢出做特殊处理。

C语言代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
#include <stdio.h>
#define LONG long long int

// 将字符串s按进制radix转化为十进制整数
LONG toDecimal(char* s,LONG radix)
{
int i;
LONG result = 0;
for(i=0;s[i]!=0;i++)
{
result *= radix;
if(s[i]>='0' && s[i]<='9')
result += s[i] - '0';
else
result += s[i] - 'a' + 10;
if(result < 0) return -1; // overflow
}
return result;
}

// 求出目标数的最小进制
LONG getMinRadix(char* s)
{
LONG result = 0;
int i;
for(i=0;s[i]!=0;i++)
{
if(result<s[i])
result = s[i];
}
if(result>='0' && result<='9')
return result - '0' + 1;
else return result - 'a' + 10 + 1;
}

int main()
{
char s1[11],s2[11];
LONG tag,radixSrc;
scanf("%s%s%lld%lld",s1,s2,&tag,&radixSrc);
LONG decNumSrc;
char *sNumSrc,*sNumTar;
if(tag==1)
{
sNumSrc = s1;
sNumTar = s2;
}
else
{
sNumSrc = s2;
sNumTar = s1;
}

decNumSrc = toDecimal(sNumSrc,radixSrc);
if(decNumSrc == -1) return 0; // 源操作数溢出

LONG minRadixTar = getMinRadix(sNumTar);
LONG maxRadixTar = decNumSrc + 1;

LONG radixTar;
while(maxRadixTar>=minRadixTar)
{
radixTar = (maxRadixTar + minRadixTar)/2;
LONG decNumTar = toDecimal(sNumTar,radixTar);
if(decNumTar ==-1 || decNumTar > decNumSrc)
maxRadixTar = radixTar - 1;
else if(decNumTar < decNumSrc)
minRadixTar = radixTar + 1;
else
{
printf("%lld\n",radixTar);
return 0;
}
}
if(maxRadixTar < minRadixTar)
{
printf("Impossible\n");
}
return 0;
}

对溢出做了特殊处理后,终于通过全部case。但是此例有一个问题,那就是源操作数(tag标志的那个数)不能超过long long的表示范围,否则要是在那里就发生溢出的话,整个程序就没有任何意义了。关于这一点,还不能完善的解决,欢迎各位大神的完美解决方案。

用Java也实现了一下,感觉跟用C语言却别不大,但效率要低一些了,还是要注意特殊处理溢出的问题,数据类型用64位的long。

Java代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
import java.util.Scanner;
public class Main
{
public static long toDecimal(String s,long radix)
{
int len = s.length();
byte[] str = s.getBytes();
long result = 0;
for(int i=0;i<len;i++)
{
result *= radix;
if(str[i]>='0' && str[i]<='9')
result += str[i] - '0';
else
result += str[i] - 'a' + 10;
if(result < 0) return -1; // overflow
}
return result;
}

public static long getMinRadix(String s)
{
int len = s.length();
byte[] str = s.getBytes();
long result = 0;
for(int i=0;i<len;i++)
{
if(str[i] > result)
result = str[i];
}
if(result>='0' && result<='9')
return result - '0' + 1;
return result - 'a' + 10 + 1;
}

public static void main(String[] argv)
{
Scanner in = new Scanner(System.in);
String sNum1 = in.next();
String sNum2 = in.next();
long tag = in.nextInt();
long radixSrc = in.nextInt();
long nNumSrc;
String sNumSrc,sNumTar;
if(tag==1)
{
sNumSrc = sNum1;
sNumTar = sNum2;
}
else
{
sNumSrc = sNum2;
sNumTar = sNum1;
}
nNumSrc = toDecimal(sNumSrc,radixSrc);
if(nNumSrc == -1) return; // source number overflow

long minRadixTar = getMinRadix(sNumTar);
long maxRadixTar = nNumSrc + 1;
long radixTar = 0;
while(maxRadixTar>=minRadixTar)
{
radixTar = (minRadixTar + maxRadixTar)/2;
long nNumTar = toDecimal(sNumTar,radixTar);
if(nNumTar==-1 || nNumTar > nNumSrc)
maxRadixTar = radixTar - 1;
else if(nNumTar < nNumSrc)
minRadixTar = radixTar + 1;
else
{
System.out.println(radixTar);
return;
}
}
if(maxRadixTar < minRadixTar)
{
System.out.println("Impossible");
}
}
}

大家如果有更好的解决方法,欢迎讨论。