🔗 UVA-573 The Snail

tags: `模擬(Simulation)`

範例程式碼已於UVA、瘋狂程設(CPE) 上皆測試通過。(此題無 ZeroJudge )

題意

給定一組係數 $H, U, D, F$ ，其中 $H$ 為井深， $U$ 為白天上升高度， $D$ 為晚上掉落高度， $F$ 為疲勞因子。每天白天上升高度 $U$ 會隨著疲勞因子 $F$ 衰減，即 $U = U - F$ ，但不會衰減到負值。求哪一天會爬出井口，或是永遠無法爬出井口。

高度 $>H$ 才算爬出井口， $<0$ 才算掉入井底，這個訊息可能要從測試資料中才能看出來。

LuckyCat 的中文翻譯

思路：模擬(Simulation)

只要模擬每天的上升和掉落即可，但需要注意每天上升的高度最低為 $0$ ，不會衰減到負值。

複雜度分析

時間複雜度： $O(\frac{100}{F} + \frac{H}{D})$ 。上升高度衰減到 $0$ 需要 $\lceil\frac{100}{F}\rceil$ 天，此時會開始掉落，而掉落到井底最多需要 $\lceil\frac{H}{D}\rceil$ 天。
空間複雜度： $O(1)$ 。

while True:
    H, U, D, F = map(int, input().split())
    if H == 0 and U == 0 and D == 0 and F == 0:
        break
    f = U * F / 100 # fatigue factor
    ans, cur = 0, 0 # day, current height
    while cur >= 0 and cur <= H:
        ans += 1
        cur += U
        U = max(0, U - f) # 上升高度衰減，但不會衰減到負值
        if cur > H: # 爬出井口
            flag = True
            break
        cur -= D # 掉落高度
        if cur < 0:
            flag = False
            break
    print("success" if flag else "failure", "on day", ans)

#include <bits/stdc++.h>
using namespace std;
#define endl '\n'

int main() {
    ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
    int H, U, D, F;
    while (cin >> H >> U >> D >> F && (H || U || D || F)) {
        double cur = 0, up = U, f = U * F / 100.0; // current height, increase height, fatigue factor
        int ans = 0; // day
        bool flag = false;
        while (cur >= 0 && !flag) {
            ans += 1;
            cur += up;
            up = max(0.0, up - f); // 上升高度衰減，但不會衰減到負值
            if (cur > H) flag = true; // 爬出井口
            cur -= D; // 掉落高度
        }
        cout << (flag ? "success" : "failure") << " on day " << ans << endl;
    }
    return 0;
}