【PAT-Advanced】1010 Radix

发表于 | 分类于 ， | | 阅读次数:

Problem

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 $N_1$ and $N_2$, 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:

$N_1$ $N_2$ 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


Solution

这题的意思和解题思路不太难，但是巨坑，过了很多次才过去。

题目意思大概就是进制转换，需要注意的有以下几个点

  • radix和N可能会很大，要用long long而不是int

  • 可能会出现多种可能进制的情况，这种情况下输出最小的radix。例如8 8 1 10这组输入，可以是9以上任何进制，这时输出9。要注意的是，只有输入的未知进制的数是一位数的时候可能会出现这种情况，因此只要在输入是一位数的时候考虑出现多种可能进制。

  • 还是上面那个例子，8 8 1 10的输入，输出是9，因为最大位数是8，只有在9以上的进制会出现8这个数字。这意味着要做一个判定，根据出现的数字或字符找到可能的最小进制。

  • 最简单的方式是在范围内线性遍历找到对应的radix，做法如下：

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    for(radix2 = minR(N2); ; radix2++){
            dec2 = toDec(N2, radix2);
            if(dec1 == dec2){
                cout << radix2 << endl;
                break;
            }else if(dec2 > dec1 || radix2 > dec1){
                cout << "Impossible" << endl;
                break;
            }
        }

    其中minR用于做上一个注意点的判定，toDec用于把不同进制的数转为十进制，dec1是已知进制的数的十进制值。

    这样做会有一个测试点过不去，显示运行超时。问题在于线性遍历太慢，可以用二分遍历降低复杂度。在改为二分遍历之后能够过这个点。

  • 在判断的时候要注意溢出问题，如果溢出则要减小二分范围的上界。

实现代码如下：

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
81
82
83
84
85
86
#include <bits/stdc++.h>
using namespace std;

string N1, N2;
long long tag, radix, radix2 = -1;
long long dec1, dec2;

//将字符转换为对应的数字
int toNum(char c)
{
    if(c <= '9'){
        return c - '0';
    }else{
        return c - 'a' + 10;
    }
    
}

//求十进制值
long long toDec(string num, long long radix)
{
    long long dec = 0;
    for(int i=0; i<num.length(); i++){
        int next = toNum(num[i]);
        dec = dec * radix + next;
    }
    return dec;
}

//找到当前数字可能的最小进制，例如12abf最小只能是十六进制
long long minR(string num){
    long long ret;
    char maxc = '0';
    for(int i=0; i<num.length(); i++){
        maxc = max(maxc, num[i]);
    }
    ret = toNum(maxc) + 1;
    if(ret < 2){
        ret = 2;
    }
    return ret;
}

int main(int argc, const char * argv[]) {
    cin >> N1 >> N2 >> tag >> radix;
    //让已知进制的数作为N1
    if(tag == 2){
        string temp = N1;
        N1 = N2;
        N2 = temp;
    }
  
    dec1 = toDec(N1, radix);
    //二分遍历
    long long rmin = minR(N2);
    long long rmax = dec1;
    long long r;
    int first = toNum(N2[0]);
    //如果只有一位数，且符合，即可能有多种进制情况，输出最小
    if(N2.length() == 1 && dec1 == first){
        radix2 = rmin;
    }else{
        while(rmin <= rmax){
            r = (rmin + rmax) / 2;
            dec2 = toDec(N2, r);
            //如果溢出，缩小上界
            if(dec2 < 0){
                rmax = r - 1;
            }else if(dec2 == dec1){
                radix2 = r;
                break;
            } else if(dec2 > dec1){
                rmax = r - 1;
            }else if (dec2 < dec1){
                rmin = r + 1;
            }
        }
    }

    if(radix2 == -1){
        cout << "Impossible" << endl;
    }else{
        cout << radix2 << endl;
    }
    return 0;
}