PAT-甲级 1010 Radix (25分)【二分】

77 阅读 0 评论 51 点赞

我是靠谱客的博主稳重美女，最近开发中收集的这篇文章主要介绍PAT-甲级 1010 Radix (25分)【二分】，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

1010 Radix (25分)

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

题意：给出4个数n1,n2,tag,radix，当tag=1时，n1的进制为radix，如果n2在某个进制下，能等于n1，就输出这个数。如果有多个答案，输出最小的；如果没有答案，输出Impossible

思路：把n1和n2转换成10进制比较。当tag=1的时候；，将radix进制的n1转换成十进制数t1；

然后开始分析n2，比如n2=281，最大字符是"8"，那么显然，n2的进制最小就为8+1=9，

那n2的的进制最大为多少呢，假设n1=25，radix=10，则n2的进制最大也只能到25。（当n2为25进制时，n2转换成10进制, ${color{Blue} 1*25^0}+{color{Red}8*25^1 }+2*25^2$ ,结果肯定大于2了5，后面的进制结果只会更大）

当tag=2的时候，交换n1和n2的值；

注意点：假设n2的区间范围是 $[begin,end]$

①当n2=0时，begin不能0+1=1，因为进制最小为2，所以begin至少等于2

②当n2为多位数的时候，n2的进制数最大为10进制的n1；但当n2只有一位数的时候，比如案例：7 7 1 10，显然n2的进制数为7+1=8；兼顾以上两点，end可以取：10进制的n1+1

③从begin遍历到end，如果某个进制的n2 转换成10进制 = 10进制的n1，这个数就是答案。

坑点：

①最小进制不能小于2，最大进制不能拘谨于36

②从begin到end遍历，线性遍历测试点8会超时，要用二分查找。

③有的案例数字会很大，要用long long储存；有时候long long也会溢出成负数（很多测试点都溢出了），所以代码里二分查找在判断边界时有一句if(t2<0)。这里没考虑t1转换成10进制时溢出的情况，好像题目中也没有类似 zzzzz zzzzz 1 1000000000的案例

#include <bits/stdc++.h>
using namespace std;

typedef long long LL;
LL to10(string n, int radix) {
    reverse(n.begin(), n.end());
    LL ans = 0;
    for (int i = 0; i < n.size(); i++) {
        if (isdigit(n[i]))
            ans += (n[i] - '0') * pow(radix, i);
        else
            ans += (n[i] - 87) * pow(radix, i);
    }
    return ans;
}
int getmin(string s) {
    int maxn = -1;
    for (int i = 0; i < s.size(); i++) {
        maxn = max(maxn, isdigit(s[i]) ? s[i] - 48 : s[i] - 87);
    }
    return maxn + 1 < 2 ? 2 : maxn + 1;
}
LL find(LL left, LL right, string s, LL t1) {
    LL mid = (left + right) >> 1;
    if (left > right)
        return -1;
    LL t2 = to10(s, mid);

    if (t2 < 0 || t2 > t1) {
        return find(left, mid - 1, s, t1);
    } else if (t2 < t1) {
        return find(mid + 1, right, s, t1);
    } else {
        return mid;
    }
}
int main() {
    string n1, n2;
    int tag, radix;
    cin >> n1 >> n2 >> tag >> radix;
    if (tag == 2)
        swap(n1, n2);

    LL t1 = to10(n1, radix);
    LL begin = getmin(n2);
    LL end = t1 + 1;

    int ans = find(begin, end, n2, t1);

    if (ans == -1) {
        cout << "Impossiblen";
    } else {
        cout << ans << endl;
    }
    system("pause");
}