首页 > 代码库 > PAT 1010 Radix

PAT 1010 Radix

2024-07-27 08:21:22   219人阅读

过了一天感觉没干什么，想刷一发题弥补一下，正在考虑去做哪道，室友说去试试PAT 1010，果然当年自己直接跳过了这题，一看这通过率（0.07）有点夸张了。题目是已知一个数，求另外一个数的基数，使得这两个数数值上相等。很自然的考虑到使用二分搜索来确定这个基数，数字表示使用[0-9a-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\n", bradix);        } else {            // only one digit, so choose a smallest valid radix            printf("%d\n", 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\n");    } else {        printf("%d", res);    }    return 0;}

 

PAT 1010 Radix


联系
我们