题目#

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 $\left \{ 0-9, a-z \right \}$ 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 $N_1$ if “tag” is 1, or of $N_2$if “tag” is 2.

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

解法#

String Convert to Long#

就是输入数据，由于数据中可能含有字母，仍存储为String格式。对已经给出进制的树先算出其对应的十进制数是多少：

//已知字符串和进制，算出对应的十进制数
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;
}

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

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

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;

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. $N_1$和$N_2$一样时，应该输出其中最大字符所代表的数值再+1；

代码实现#

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;
    }
}