PAT 1010 Radix (25)

本文主要是介绍PAT 1010 Radix (25)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

1010 Radix (25)（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 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:

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

Sample Input 3:

12 c 1 10

Sample Output 3:

13

思路：

这真是我做到现在觉得最坑的一题……虽然写了是{0~9,a~z}，但是进制远远不止36！因为数字会很大，所以这里用二分查找来做，于是就要确定左右两端的值。n2中最大的字符对应的值+1是查找的下界，需要注意的是如果字符全是‘0’的话下界为2，因为最小是二进制。至于上界的话，n2的进制肯定不会超过n1进制（是n1进制不是n1的进制）。一直用long long也WA了好多遍，最后翻了别人的才知道要unsigned long long。

代码：

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <cctype>
#include <climits>
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <queue>
#include <stack>
#include <map>  
#include <set>
using namespace std;int ctoi[127];unsigned long long convert(string s, int r)
{long long n = 0;for (int i = 0; i <s.length(); i++)n = n*r+ctoi[(s[i])];return n;
}int find_left(string s)
{char max = 0;for (int i = 0; i < s.length(); i++){if (s[i] > max)max = s[i];}if (max == '0')return 2;elsereturn ctoi[max] + 1;
}int main()
{for (int i = '0'; i <= '9'; i++)ctoi[i] = i - '0';for (int i = 'a'; i <= 'z'; i++)ctoi[i] = i - 'a' + 10;string s1, s2;int tag, radix;unsigned long long n1, n2, l, r, m;cin >> s1 >> s2 >> tag >> radix;if (tag == 2)swap(s1, s2);n1 = convert(s1, radix);l = find_left(s2);r = n1;while (l < r){m = (l + r) / 2;n2 = convert(s2, m);if (n2 == n1)l = r = m;else if (n2 > n1)r = m - 1;elsel = m + 1;}if (convert(s2, l) == n1)cout << l << endl;elsecout << "Impossible" << endl;return 0;
}

 

这篇关于PAT 1010 Radix (25)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---