title
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
solution
二分法
最小的就是n2中最大的数字+1
最大的就是max(left,a)+1
注意溢出问题
#include<iostream>
#include<algorithm>
#include<string.h>
using namespace std;
int map[256];
long long toTen(char *s, long long radix) {
int n = strlen(s);
long long res = 0;
for (int i = 0; i < n; i++) {
res = res * radix + map[s[i]];
}
return res;
}
int cmp(char n2[], long long radix, long long t) {
//n2's length,toDex,
int len = strlen(n2);
long long num = toTen(n2, radix);
if (num < 0) return 1;
if (num < t) return -1;
return (t == num) ? 0 : 1;
}
int main() {
#ifdef JUDGE
freopen("D:\\a.txt", "r", stdin);
//freopen("D:\b.txt", "r", stdout);
#endif
long long tag, radix;
char n1[20], n2[20];
for (int i = '0'; i <= '9'; i++) {
map[i] = i - '0';
}
for (int i = 'a'; i <= 'z'; i++) {
map[i] = i - 'a' + 10;
}
scanf("%s %s %lld %lld", n1, n2, &tag, &radix);
if (tag == 2) {
swap(n1, n2);
}
long long a = toTen(n1, radix);
int n = strlen(n2);
int maxDigit = -1;
for (int i = 0; i < n; i++) {
if (map[n2[i]]>maxDigit) {
maxDigit = map[n2[i]];
}
}
long long left = maxDigit + 1;
long long right = max(left, a) + 1;
long long mid;
#ifdef JUDGE
cout << "调试内容：" << endl;
cout << left << " " << right << endl;
cout << "调试内容结束" << endl << endl;
#endif
while (left <= right) {
mid = (left + right) / 2;
long long b = toTen(n2, mid);
if (a == b) {
printf("%lld", mid);
return 0;
}
else if (a < b||b<0) {//b<0 reprents 溢出
right = mid - 1;
}
else {
left = mid + 1;
}
//int flag = cmp(n2, mid, a);
//if (flag == 0) {
// printf("%lld", mid);
// break;
//}
//else if (flag == -1) {
// left = mid + 1;
//}
//else {
// right = mid - 1;
//}
}
printf("Impossible");
}
第二次写
主要要全用longlong否则有一个不通过，因为mid的问题
#include<iostream>
#include<algorithm>
#include<string.h>
#include<string>
using namespace std;
int toInt(char c) {
if (isdigit(c)) {
return c - '0';
}
else {
return c - 'a' + 10;
}
}
char toChar(int i) {
if (i < 10) {
return i + '0';
}
else {
return i - 10 + 'a';
}
}
long long toTen(string s, long long radix) {
long long res = 0;
for (int i = 0; i < s.length(); i++) {
res = res * radix + toInt(s[i]);
}
return res;
}
//int cmp(const string s, int radix, const long long b) {
// long long a = toTen(s, radix);
// if (a < 0)
// return 1;
// if (a == b) {
// return 0;
// }
// return a < b ? -1 : 1;
//}
int main() {
string n1, n2;
int tag, radix;
cin >> n1 >> n2 >> tag >> radix;
if (tag == 2)
swap(n1, n2);
long long a = toTen(n1, radix);
int maxdigit = -1;
for (int i = 0; i < n2.length(); i++) {
maxdigit = max(maxdigit, toInt(n2[i]));
}
long long left = maxdigit + 1;
long long right = max(left, a) + 1;
while (left <= right) {
long long mid = (left + right) / 2;
long long b = toTen(n2, mid);
if (a == b) {
cout << mid;
return 0;
}
else if (a < b || b < 0) {
right = mid - 1;
}
else {
left = mid + 1;
}
}
cout << "Impossible";
return 0;
}