-
Notifications
You must be signed in to change notification settings - Fork 0
/
1010.cpp
64 lines (61 loc) · 2.06 KB
/
1010.cpp
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
#include<iostream>
#include<string>
using namespace std;
long long stringToint(string n, int radix) {
long long number = 0;
string::iterator it = n.begin();
string::iterator end = n.end();
for(; it != end; it++) {
number *= radix;
if(number < 0) return -1887415158;
if((*it) <= '9' && (*it) >= '0' && (*it) - '0' >= radix) return -1887415157;
else if((*it) >= 'a' && (*it) - 'a' + 10 >= radix) return -1887415157;
else if((*it) <= '9' && (*it) >= '0') number += (*it) - '0';
else number += (*it) - 'a' + 10;
if(number < 0) return -1887415158;
}
return number;
}
int binarySearch(string s, long long number, long long left, long long right) {
if(left > right || left < 2) return 0;
long long mid = (left + right) / 2;
// cout << left << " " << mid << " " << right <<endl;
long long n = stringToint(s, mid);
// cout << n << " " << number << endl;
// cout << "-------------------" << endl;
if(n == -1887415157) {
return binarySearch(s, number, mid + 1, right);
}
else if(n == -1887415158) {
int end = binarySearch(s, number, left, mid - 1);
if(end) return end;
else return binarySearch(s, number, mid + 1, right);
}
else if(n == number) {
int end = binarySearch(s, number, left, mid - 1);
if(end) return end;
else return mid;
}
else if (n < number) return binarySearch(s, number, mid + 1, right);
else return binarySearch(s, number, left, mid - 1);
}
int main() {
string number1, number2;
int tag, num_radix;
cin >> number1 >> number2;
cin >> tag >> num_radix;
if(tag == 1) {
long long n1 = stringToint(number1, num_radix);
int radix = binarySearch(number2, n1, 2, n1);
if(radix) cout << radix;
else cout << "Impossible";
return 0;
}
if(tag == 2) {
long long n2 = stringToint(number2, num_radix);
int radix = binarySearch(number1, n2, 2, n2);
if(radix) cout << radix;
else cout << "Impossible";
return 0;
}
}