Processing math: 100%

熱門文章

2025年5月5日 星期一

ZeroJudge 解題筆記:k520. P8.幸運基數 (Base)

作者:王一哲
日期:2025年5月5日



ZeroJudge 題目連結:k520. P8.幸運基數 (Base)

解題想法


我在這題卡了很久,一直想不出比較有效率的寫法。由題目的敘述可知,如果要把10進位制的數字 n 換成 k 進位制表示,而且轉換後每個位數都是 1,一定會有的解是 k=n1,轉換後為 11,如果 k 越小,轉換後的位數越多。我有試著把 3n1000 之中 kn1 的數字列出來,但看不出規律。

(7, 2), (13, 3), (15, 2), (21, 4), (31, 2), (31, 5), (40, 3), (43, 6), (57, 7), (63, 2),
(73, 8), (85, 4), (91, 9), (111, 10), (121, 3), (127, 2), (133, 11), (156, 5), (157, 12), (183, 13), 
(211, 14), (241, 15), (255, 2), (259, 6), (273, 16), (307, 17), (341, 4), (343, 18), (364, 3), (381, 19),
(400, 7), (421, 20), (463, 21), (507, 22), (511, 2), (553, 23), (585, 8), (601, 24), (651, 25), (703, 26),
(757, 27), (781, 5), (813, 28), (820, 9), (871, 29), (931, 30), (993, 31)

後來想到,如果 k 越小,轉換後的位數越多,那就先算出 2 進位制的位數,然後位置依序遞減到 2 為止,每次再用二分搜尋法,在 low=2,high=n1 之間找解,雖然有很多次不必要的計算,但至少能正確地找到答案。

Python 程式碼


使用時間約為 33 ms,記憶體約為 3.4 MB,通過測試。
import sys, math

# 檢查以 base 為底,在指定位數 digit 的值與 num 的大小關係
def check(num, base, digit):
    power, total = 1, 0  # 目前的次方,加總
    for i in range(digit):  # 從個位數開始往左計算 
        total += power  # 更新 total
        power *= base  # 更新 power 為 base**(i+1)
        if total > num: return 1  # 如果 total 大於 num,回傳 1,跳出函式
    if total == num: return 0  # 如果最後 total 等於 num,回傳 0
    return -1  # 否則回傳 -1

for line in sys.stdin:
    n = int(line)  # 要找基底的數字 n
    ans = n-1  # 答案預設為 n-1
    digitmax = math.ceil(math.log(n, 2))  # 最多的位數
    for digit in range(digitmax, 1, -1):  # 依序檢查最多位數到 2 位數
        low, high = 2, n-1  # 下限 2,上限 n-1
        while low <= high:  # 當 low 小於等於 high,繼續執行
            mid = (high - low)//2 + low  # 取中間值
            state = check(n, mid, digit)  # 呼叫 check 檢查大小關係
            if state == 0:  # 找到解,更新 ans 為較小的值,降低 high
                ans = min(ans, mid); high = mid-1
            elif state == 1: high = mid-1 # mid 太大,降低 hight
            else: low = mid+1  # mid 太小,提高 low
    print(ans)  # 印出答案

改成先檢查 2,使用時間約為 30 ms,記憶體約為 3.4 MB,通過測試。
import sys, math

# 檢查以 base 為底,在指定位數 digit 的值與 num 的大小關係
def check(num, base, digit):
    power, total = 1, 0  # 目前的次方,加總
    for i in range(digit):  # 從個位數開始往左計算 
        total += power  # 更新 total
        power *= base  # 更新 power 為 base**(i+1)
        if total > num: return 1  # 如果 total 大於 num,回傳 1,跳出函式
    if total == num: return 0  # 如果最後 total 等於 num,回傳 0
    return -1  # 否則回傳 -1

for line in sys.stdin:
    n = int(line)  # 要找基底的數字 n
    ans = n-1  # 答案預設為 n-1
    digitmax = math.ceil(math.log(n, 2))  # 最多的位數
    if check(n, 2, digitmax) == 0:  # 如果 2 是解,一定是最小值,不需要檢查其它的數字
        ans = 2
    else:
        for digit in range(digitmax, 1, -1):  # 依序檢查最多位數到 2 位數
            low, high = 2, n-1  # 下限 2,上限 n-1
            while low <= high:  # 當 low 小於等於 high,繼續執行
                mid = (high - low)//2 + low  # 取中間值
                state = check(n, mid, digit)  # 呼叫 check 檢查大小關係
                if state == 0:  # 找到解,更新 ans 為較小的值,降低 high
                    ans = min(ans, mid); high = mid-1
                elif state == 1: high = mid-1 # mid 太大,降低 hight
                else: low = mid+1  # mid 太小,提高 low
    print(ans)  # 印出答案


C++ 程式碼


使用時間約為 2 ms,記憶體約為 140 kB,通過測試。可能是因為我先檢查了 2 是否為解,如果 2 不是解才檢查其它的數值,少了很多次運算,少存了一些東西,使用的記憶體反而特別少。
#include <cstdio>
#include <cmath>
#include <algorithm>
typedef long long LL;
using namespace std;

/* 檢查以 base 為底,在指定位數 digit 的值與 num 的大小關係 */
int check(LL num, LL base, LL digit) {
    LL power = 1, total = 0;  // 目前的次方,加總
    for(LL i=0; i<digit; i++) {  // 從個位數開始往左計算 
        total += power;  // 更新 total
        power *= base;  // 更新 power 為 base**(i+1)
        if (total > num) return 1;  // 如果 total 大於 num,回傳 1,跳出函式
    }
    if (total == num) return 0;  // 如果最後 total 等於 num,回傳 0
    return -1;  // 否則回傳 -1
}

int main() {
    LL n;  // 要找基底的數字 n
    while(scanf("%lld", &n) != EOF) {
        LL ans = n-1;  // 答案預設為 n-1
        int digitmax = ceil(log2(n));  // 最多的位數
        if (check(n, 2, digitmax) == 0) {
            ans = 2;
        } else {
            for(LL digit=digitmax; digit > 1; digit--) {  // 依序檢查最多位數到 2 位數
                LL low = 2, high = n-1;  // 下限 2,上限 n-1
                while(low <= high) {  // 當 low 小於等於 high,繼續執行
                    LL mid = (high - low)/2 + low;  // 取中間值
                    LL state = check(n, mid, digit);  // 呼叫 check 檢查大小關係
                    if (state == 0) {  // 找到解,更新 ans 為較小的值,降低 high
                        ans = min(ans, mid); high = mid-1;
                    } else if (state == 1) {  // mid 太大,降低 hight
                        high = mid-1;
                    } else {  // mid 太小,提高 low
                        low = mid+1;
                    }
                }
            }
        }
        printf("%lld\n", ans);  // 印出答案
    }
    return 0;
}


沒有留言:

張貼留言