ZeroJudge 解題筆記：b911. 我想跟Kevin借筷子系列4

作者：王一哲
日期：2025年8月8日


ZeroJudge 題目連結：b911. 我想跟Kevin借筷子系列4

解題想法

先列出幾種可能性

1. n = 0, data = [0], ans = 0
2. n = 1, data = [1], ans = 1
3. n = 2, data = [1, 2] => [0, 1] => [0, 0], ans = 2
4. n = 3, data = [1, 2, 3] => [1, 0, 1] => [0, 0, 0], ans = 2
5. n = 4, data = [1, 2, 3, 4] => [1, 0, 1, 2] => [0, 0, 0, 1] => [0, 0, 0, 0], ans = 3
6. n = 5, data = [1, 2, 3, 4, 5] => [1, 2, 0, 1, 2] => n = 2 的狀況，ans = 1 + 2 = 3
7. n = 6, data = [1, 2, 3, 4, 5, 6] => [1, 2, 0, 1, 2, 3] => n = 3 的狀況，ans = 1 + 2 = 3
8. n = 7, data = [1, 2, 3, 4, 5, 6, 7] => [1, 2, 3, 0, 1, 2, 3] => n = 3 的狀況，ans = 1 + 2 = 3
9. n = 8, data = [1, 2, 3, 4, 5, 6, 7, 8] => [1, 2, 3, 0, 1, 2, 3, 4] => n = 4 的狀況，ans = 1 + 3 = 4

找出規律，數量 n 如果可以除以 2 則 ans 加 1，直到 n = 1 時 ans 加 1 或是 n = 2 時 ans 加 2。

Python 程式碼

使用時間約為 24 ms，記憶體約為 3.4 MB，通過測試。

import sys

for line in sys.stdin:
    n = int(line)
    ans = 0
    while n >= 1:
        if n == 1:
            ans += 1
            break
        elif n == 2:
            ans += 2
            break
        else:
            ans += 1
            n //= 2
    print(ans)

與上方的寫法邏輯相同，但改用遞迴，使用時間約為 24 ms，記憶體約為 3.4 MB，通過測試。

import sys

for line in sys.stdin:
    n = int(line)
    def solve(x, a=0):
        if x == 1: return 1
        if x == 2: return 2
        return 1 + solve(x//2, a)
    # end of def
    print(solve(n))

C++ 程式碼

使用時間約為 2 ms，記憶體約為 316 kB，通過測試。

#include <iostream>
using namespace std;

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    int n;
    while(cin >> n) {
        int ans = 0;
        while(n >= 1) {
            if (n == 1) {
                ans++; break;
            } else if (n == 2) {
                ans += 2; break;
            } else {
                ans++; n /= 2;
            }
        }
        cout << ans << "\n";
    }
    return 0;
}

使用時間約為 2 ms，記憶體約為 320 kB，通過測試。

#include <iostream>
using namespace std;

int solve(int x, int a=0) {
    if (x == 1) return 1;
    else if (x == 2) return 2;
    return 1 + solve(x/2, a);
}

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    int n;
    while(cin >> n) cout << solve(n) << "\n";
    return 0;
}

<