该题未全部完成，未通过全部测例 20/25

这道题目是PAT甲级习题中通过率最低的一道题，通过率只有$0.08$。我暂时也未能通过全部测例，还差4个测例。应该是边界条件未考虑充分。

题目

Each input file contains one test case. Each case occupies a line which contains 4 positive integers:

$N_1$ $N_2$ tag radix

Here $N_1$ and $N_2$ 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.

中文大意：
输入4个数
其中第四个数表示第三个数所指的那个数$N$的进制，现在来判断另一个数$M$在哪一种进制下回合$N$相同，若存在则输出进制，否则输出”Impossible”。

解法

String Convert to Long

就是输入数据，由于数据中可能含有字母，仍存储为

1
2
3
4
5
6
7
8
9
10
11

```java
//已知字符串和进制，算出对应的十进制数
public static long strToLong(String str,long radix){
    long res=0;
    int tmp=0;
    for(int i=str.length()-1;i>=0;i--){
        res+=map.get(str.charAt(i))*Math.pow(radix,tmp++);
    }
    return res;
}

获得未知进制数中最大的字符所代表的十进制数

因为进制数一定要大于最大的字符，所以可以通过这一步获得进制的下限

1
2
3
4
5
6
7
8
String resNumStr = dataStr[resRadixNumPosi];
    //获取未知进制数中最大的字符所代表的十进制数
    int biggestCharInResNumStr = map.get(resNumStr.charAt(0));
    for (int i = 0; i < resNumStr.length(); i++) {
        if (map.get(resNumStr.charAt(i)) > biggestCharInResNumStr) {
            biggestCharInResNumStr = map.get(resNumStr.charAt(i));
        }
    }

二分查找

下限即上一步所求出的数+1
上限即为已知进制的数

退出条件:
若上下限相同，检查对应两个数在该进制是否相同
若下限大于上限，输出Impossible; return;

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
public static void findRadix(long num,String str,long radixBegin,long radixEnd){
    if(radixBegin>radixEnd){
        System.out.println("Impossible");
        return;
    }
    if(radixBegin==radixEnd){
        if(strToLong(str,radixBegin)==num){
            System.out.println(radixBegin);
            return;
        }else{
            System.out.println("Impossible");
            return;
        }
    }
    long radixMiddle=(radixBegin+radixEnd)>>1;
    long middleRadixNum=strToLong(str,radixMiddle);
    if(middleRadixNum>num){
        findRadix(num,str,radixBegin,radixMiddle);
    }else if(middleRadixNum==num){
        System.out.println(radixMiddle);
        return;
    }else{
        findRadix(num,str,radixMiddle+1,radixEnd);
    }


}

边界条件

  1. N1和N2一样时，应该输出其中最大字符所代表的数值再+1；

代码实现

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
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
package PAT;

import java.util.HashMap;
import java.util.Scanner;

/**
 * Created by xgh on 2016/2/21.
 */
public class _1010_Radix_25{
    private static HashMap<Character,Integer> map=new HashMap<Character, Integer>();

    public static void main(String[] args) {

        Scanner in = new Scanner(System.in);
        String[] dataStr = (in.nextLine()).split(" ");
        int charRepNum = 10;
        for (char i = 'a'; i <= 'z'; i++) {
            map.put(i, charRepNum++);
        }
        for (int i = 0; i < 9; i++) {
            map.put((char) (i + 48), i);
        }


        int givenRadixNumPosi = Integer.parseInt(dataStr[2]);
        long givenRadix = Integer.parseInt(dataStr[3]);

        long aaa = 0;
        long givenNum = 0;
        String givenNumStr = dataStr[givenRadixNumPosi - 1];
//        System.out.println(givenNumStr);
//        System.out.println(givenRadixNumPosi-1);
//        for(char e:map.keySet()){
//            System.out.println(e+" ==== "+map.get(e));
//        }
        for (int i = givenNumStr.length() - 1; i >= 0; i--) {
            givenNum += map.get(givenNumStr.charAt(i)) * Math.pow(givenRadix, aaa++);
        }

        int resRadixNumPosi = 0;
        if (givenRadixNumPosi == 1) {
            resRadixNumPosi = 1;
        } else {
            resRadixNumPosi = 0;
        }

        String resNumStr = dataStr[resRadixNumPosi];
        int biggestCharInResNumStr = map.get(resNumStr.charAt(0));
        for (int i = 0; i < resNumStr.length(); i++) {
            if (map.get(resNumStr.charAt(i)) > biggestCharInResNumStr) {
                biggestCharInResNumStr = map.get(resNumStr.charAt(i));
            }
        }


        if(strToLong(resNumStr,biggestCharInResNumStr+1)==givenNum){
            System.out.println(biggestCharInResNumStr+1);
            return;
        }

//        System.out.println(Integer.parseInt("ab"));
//        System.out.println(givenNum);
//        System.out.println(resNumStr);
//        System.out.println(givenRadix+1);
//        System.out.println(biggestCharInResNumStr+1);

        findRadix(givenNum,resNumStr,biggestCharInResNumStr+1,givenNum+1);
    }


    public static void findRadix(long num,String str,long radixBegin,long radixEnd){
        if(radixBegin>radixEnd){
            System.out.println("Impossible");
            return;
        }
        if(radixBegin==radixEnd){
            if(strToLong(str,radixBegin)==num){
                System.out.println(radixBegin);
                return;
            }else{
                System.out.println("Impossible");
                return;
            }
        }
        long radixMiddle=(radixBegin+radixEnd)>>1;
        long middleRadixNum=strToLong(str,radixMiddle);
        if(middleRadixNum>num){
            findRadix(num,str,radixBegin,radixMiddle);
        }else if(middleRadixNum==num){
            System.out.println(radixMiddle);
            return;
        }else{
            findRadix(num,str,radixMiddle+1,radixEnd);
        }


    }

    public static long strToLong(String str,long radix){
        long res=0;
        int tmp=0;
        for(int i=str.length()-1;i>=0;i--){
            res+=map.get(str.charAt(i))*Math.pow(radix,tmp++);
        }
        return res;
    }
}