PAT 1010 1010. Radix (25)
Sample Input 1:
6 110 1 10Sample Output 1:
2Sample Input 2:
1 ab 1 2Sample Output 2:
Impossible
刚开始以为此题的范围会超过long long int，试过后发现并没有。另外题目说字符串里面的数字只有{0-9,a-z}，让我以为radix的范围不会超过36，后来发现错了。更改后提交，发现有一个case超时了，估计这个case里的radix非常大，于是radix也采用long long int，并且采用二分搜索，这才解决超时问题。注意这VS下long long int应该定义成__int64，输入输出格式为%I64d。
代码
1 #define __int64 long long
2 #include <stdio.h>
3 #include <string.h>
4
5 long long calculateFunc(char *,long long);
6 int maxDigit(char *);
7 int char2num(char);
8 int main()
9 {
10 long long N1,N2,radix;
11 int tag;
12 char str1[12],str2[12];
13 char *p1,*p2;
14 while(scanf("%s %s",str1,str2) != EOF){
15 scanf("%d%I64d",&tag,&radix);
16 if(tag == 1){
17 p1 = str1;
18 p2 = str2;
19 }
20 else{
21 p1 = str2;
22 p2 = str1;
23 }
24 N1 = calculateFunc(p1,radix);
25 int radixMin = maxDigit(p2) + 1;
26 if (radixMin < 2)
27 radixMin = 2;
28 int strN = strlen(p2);
29 if(strN == 1){
30 N2 = char2num(*p2);
31 if(N2 == N1){
32 printf("%I64d ",N2+1);
33 }
34 else{
35 printf("Impossible ");
36 }
37 continue;
38 }
39 long long i = radixMin;
40 N2 = calculateFunc(p2,i);
41 int flag = 0;
42 while(N2 <= N1){
43 if(N1 == N2){
44 printf("%I64d ",i);
45 flag = 1;
46 break;
47 }
48 i *= 2;
49 N2 = calculateFunc(p2,i);
50 }
51 if(!flag){
52 long long s = i / 2,e = i;
53 long long mid;
54 while(e >= s){
55 mid = (s + e) / 2;
56 N2 = calculateFunc(p2,mid);
57 if(N1 == N2){
58 printf("%I64d ",mid);
59 flag = 1;
60 break;
61 }
62 else if (N1 > N2){
63 s = mid + 1;
64 }
65 else{
66 e = mid - 1;
67 }
68 }
69 if(!flag){
70 printf("Impossible ");
71 }
72 }
73 }
74 return 0;
75 }
76
77 long long calculateFunc(char *p,long long radix)
78 {
79 int n = strlen(p);
80 int i;
81 long long N = 0;
82 for(i=0;i<n;++i){
83 N = N * radix + char2num(*(p+i));
84 }
85 return N;
86 }
87
88 int maxDigit(char *p)
89 {
90 int n = strlen(p);
91 int i;
92 int m = -1;
93 int t;
94 for(i=0;i<n;++i){
95 t = char2num(*(p+i));
96 if (t > m)
97 m = t;
98 }
99 return m;
100 }
101
102 int char2num(char c)
103 {
104 if(c >= '0' && c <= '9')
105 return c - '0';
106 else if(c >= 'a' && c <= 'z')
107 return c - 'a' + 10;
108 else
109 return -1;
110 }
2 #include <stdio.h>
3 #include <string.h>
4
5 long long calculateFunc(char *,long long);
6 int maxDigit(char *);
7 int char2num(char);
8 int main()
9 {
10 long long N1,N2,radix;
11 int tag;
12 char str1[12],str2[12];
13 char *p1,*p2;
14 while(scanf("%s %s",str1,str2) != EOF){
15 scanf("%d%I64d",&tag,&radix);
16 if(tag == 1){
17 p1 = str1;
18 p2 = str2;
19 }
20 else{
21 p1 = str2;
22 p2 = str1;
23 }
24 N1 = calculateFunc(p1,radix);
25 int radixMin = maxDigit(p2) + 1;
26 if (radixMin < 2)
27 radixMin = 2;
28 int strN = strlen(p2);
29 if(strN == 1){
30 N2 = char2num(*p2);
31 if(N2 == N1){
32 printf("%I64d ",N2+1);
33 }
34 else{
35 printf("Impossible ");
36 }
37 continue;
38 }
39 long long i = radixMin;
40 N2 = calculateFunc(p2,i);
41 int flag = 0;
42 while(N2 <= N1){
43 if(N1 == N2){
44 printf("%I64d ",i);
45 flag = 1;
46 break;
47 }
48 i *= 2;
49 N2 = calculateFunc(p2,i);
50 }
51 if(!flag){
52 long long s = i / 2,e = i;
53 long long mid;
54 while(e >= s){
55 mid = (s + e) / 2;
56 N2 = calculateFunc(p2,mid);
57 if(N1 == N2){
58 printf("%I64d ",mid);
59 flag = 1;
60 break;
61 }
62 else if (N1 > N2){
63 s = mid + 1;
64 }
65 else{
66 e = mid - 1;
67 }
68 }
69 if(!flag){
70 printf("Impossible ");
71 }
72 }
73 }
74 return 0;
75 }
76
77 long long calculateFunc(char *p,long long radix)
78 {
79 int n = strlen(p);
80 int i;
81 long long N = 0;
82 for(i=0;i<n;++i){
83 N = N * radix + char2num(*(p+i));
84 }
85 return N;
86 }
87
88 int maxDigit(char *p)
89 {
90 int n = strlen(p);
91 int i;
92 int m = -1;
93 int t;
94 for(i=0;i<n;++i){
95 t = char2num(*(p+i));
96 if (t > m)
97 m = t;
98 }
99 return m;
100 }
101
102 int char2num(char c)
103 {
104 if(c >= '0' && c <= '9')
105 return c - '0';
106 else if(c >= 'a' && c <= 'z')
107 return c - 'a' + 10;
108 else
109 return -1;
110 }