PAT 1010 Radix
14718 ワード
一日が過ぎて何もしていないような気がして、問題を補いたいと思って、どの道をするか考えています.ルームメイトはPAT 1010を試してみると言っていましたが、やはりその年は自分で直接この問題をスキップしました.この通過率(0.07)を見るとちょっと大げさです.テーマは既知の数で、別の数の基数を求めて、この2つの数の値が等しくなるようにします.2分探索を用いてこの基数を決定することを自然に考慮して、数字は[0-9 a-z]を使用することを表しています.ああ、このtmdの基数の範囲は1~36の間にあると思いがちですが、まあ、基数はこの範囲を超えることができますが、それを考慮しなければ、得られる典型的な点数の一つは19点です.しかし、基数が[1,36]の間ではこの検索範囲が小さすぎて、直接暴力が遍歴してもいいので、黙って範囲を広げて、とにかく穴の問題で、仕方なく、老女はこのように爱しています.コードは次のとおりです.
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
using namespace std;
char char2num[128];
int remove_leading_zero(char* str) {
if (str[0] == '\0') return 0;
int ri = 0, wi = 0;
while (str[ri] == '0' || str[ri] == '+' || str[ri] == '-') ri++;
int len = 0;
while ((str[wi++] = str[ri++]) != '\0') len++;
if (len == 0) {
str[0] == '0';
str[++len] = '\0';
}
return len;
}
long long value(const char* str, int len, long long radix) {
long long ret = 0;
long long r = 1;
for (int i=len - 1; i>=0; i--) {
int digit = char2num[str[i]];
// we should check the number validation
if (digit >= radix) return -1;
ret += r * digit;
r *= radix;
}
return ret;
}
int inc_cmp(char* str, int len, long long radix, long long target){
long long v = 0;
long long r = 1;
for (int i=len - 1; i>=0; i--) {
int digit = char2num[str[i]];
v += r * digit;
r *=radix;
if (v > target) {
return 1;
}
}
if (v == target) {
return 0;
} else {
return -1;
}
}
long long binary_search(char* str, int len, long long lo, long long hi, long long target){
long long mid;
lo = lo - 1;
hi = hi + 1;
while(lo + 1< hi){
mid = (lo + hi) / 2;
int res = inc_cmp(str, len, mid, target);
if(res > 0) {
hi = mid;
} else if(res < 0) {
lo = mid;
} else {
return mid;
}
}
return -1;
}
int main() {
// init char2num lookup table
for (int i=0; i<10; i++) char2num['0' + i] = i;
for (int i='a'; i<='z'; i++) char2num[i] = i - 'a' + 10;
char num1[16] = {'\0'};
char num2[16] = {'\0'};
char *pnum1 = num1, *pnum2 = num2;
int tag = 0;
long long bradix = 0;
scanf("%s%s%d%ld", num1, num2, &tag, &bradix);
// we always assure that bradix is the radix of pnum1
// and pnum2 is which we should guess its radix
if (tag != 1) {
pnum1 = num2;
pnum2 = num1;
}
int n1len = remove_leading_zero(pnum1);
int n2len = remove_leading_zero(pnum2);
long long n1 = value(pnum1, n1len, bradix);
bool is_same = !strcmp(pnum1, pnum2);
if(is_same) {
if (n1len > 1) {
// must be same radix, if digits more than one
printf("%d
", bradix);
} else {
// only one digit, so choose a smallest valid radix
printf("%d
", n1 + 1);
}
return 0;
}
long long lo = 0;
for (int i=0; i<n2len; i++) {
int d = char2num[pnum2[i]];
if (d + 1> lo) lo = d + 1;
}
long long hi = n1 > lo ? n1 : lo;
int res = binary_search(pnum2, n2len, lo, hi, n1);
if (res < 0) {
printf("Impossible
");
} else {
printf("%d", res);
}
return 0;
}