【題解】ZeroJudge d189: 11150 – Cola

【題目敘述】https://zerojudge.tw/ShowProblem?problemid=d189
【解題想法】模擬法、數值解

  • 【模擬】因為三個空瓶可以換一瓶可樂,因此最後只會剩下一個或兩個空瓶。如果剩兩個空瓶時,借一個空瓶可以多喝一瓶可樂,還可以返還一個空瓶。
  • 【數值解】先用程式跑小數據,觀察結果。ans = floor(1.5 * N)
    • N = 1; ans = 1
    • N = 2; ans = 3
    • N = 3; ans = 4
    • N = 4; ans = 6
    • N = 5; ans = 7
    • N = 6; ans = 9
    • N = 7; ans = 10
    • N = 19; ans = 28
    • N = 20; ans = 30
#include <iostream>
using namespace std;

int main() {
    int N;
    while (cin >> N){
        int ans = N;
        while (N >= 3){
            ans += N / 3;
            N = N / 3 + N % 3;
        }
        ans += (N == 2);
        cout << ans << "\n";
    }
    return 0;
}

Python code (credit: Amy Chou)

while True:
    try:
        N  = int(input())
        ans = N
        while N >= 3:
            ans += N // 3
            N = N // 3 + N % 3
        ans += (N == 2)
        print(ans)
    except:
        break
分享本文 Share with friends