【題解】ZeroJudge e183: 10940 – Throwing cards away II

【題目敘述】https://zerojudge.tw/ShowProblem?problemid=e183
【解題想法】

  • 用queue模擬紙牌操作會TLE。
  • 觀察小數字的模擬結果,然後找出規律。
    • n = [1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20]
    • ans = [1 2 2 4 2 4 6 8 2 4 6 8 10 12 14 16 2 4 6 8]
  • ans = f(n)
    • f(1) = 1
    • f(2) = 2
    • n = 偶數, f(n) = 2 * f(n/2)
    • n = 奇數, f(n) = 2 * ( f((n+1) / 2) – 1 )
#include <iostream>
using namespace std;

int func(int x){
    if (x == 1) return 1;
    if (x % 2 == 0){
        return 2 * func(x/2);
    } else {
        return 2 * (func((x+1)/2) - 1);
    }
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int n;
    while (cin >> n && n){
        cout << func(n) << "\n";
    }
    return 0;
}
分享本文 Share with friends