はまやんはまやんはまやん

hamayanhamayan's blog

Save Energy! [Codeforces Round #467 (Div. 1) A]

http://codeforces.com/contest/936/problem/A

1度スイッチを入れるとK分間稼働するストーブがある。 
自分はD分毎に部屋の様子を見に来る。
もしストーブが切れていたらストーブを着け直す。
料理をするが、ストーブが全ての時間でついていればT分、ストーブが全ての時間で消えていれば2T分で終了する。
何分の段階で料理が完了するか。

解法

http://codeforces.com/contest/936/submission/35691670

少しだけ条件を言い換えておこう。
x分ストーブがついていればx分分の料理ができるし、y分ストーブがついていればy/2分分の料理ができる。
答えは小数で答えるが、÷2となることしか無いため、全ての時間を2倍することで、全て整数で考えていくことにする。
 
コーナーになるかもしれない所を場合分けしておこう。
D % K == 0の場合はストーブが切れたら丁度様子を見に来て消せるので、全てストーブがついた状態で料理ができる。
そのため、答えはTとなる。
 
それ以外の場合は、周期を使って解いていく。
周期の長さA, そのうちストーブが着いている時間B, ストーブが消えている時間Cをまず求めよう。
K<Dの場合は、スイッチを入れると次に様子を見に来るときには消えているので、「A = D, B = K, C = A - B」
K>Dの場合は、ストーブが切れる前に何回か様子を見に来るが、様子を見に来る途中で消えてしまう。
この場合はDの倍数で初めてKを越えるポイントを探せばいいので、切り上げ的な事をする
「A = (K / D + 1) * D, B = K, C = A - B」
 
1周期で料理できる分oneはB + C/2である。
T/oneをすると何周期で料理できるかが分かる。
半端な周期は後で計算するので、切り捨てをして、半端じゃない周期は先に行っておこう。
ans = (T / one) * A
 
最後に半端な周期だけ計算するが、ストーブが着いている所で終わるか、ストーブが消えている所で終わるかでまた場合分けする。
T≦Bならストーブが着いている所で終わるので、T分の時間だけかかる。
そうでないなら、ストーブが消えている所で終わるので、B分の時間と(T - B)*2分の時間がかかる。
 
最後に2で割って答え。
(自分の答え方だと.5が出来る場合に付け加えている)

ll K, D, T;
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> K >> D >> T;

    if (K % D == 0) printf("%lld\n", T);
    else {
        K *= 2;
        D *= 2;
        T *= 2;

        ll A, B, C;

        if (K < D) {
            A = D;
            B = K;
            C = A - B;
        }
        else {
            A = (K / D + 1) * D;
            B = K;
            C = A - B;
        }

        ll one = B + C / 2;

        ll ans = 0;
        ans = (T / one) * A;
        T %= one;

        if (T <= B) ans += T;
        else {
            ans += B;
            T -= B;
            ans += T * 2;
        }

        if (ans % 2 == 1) printf("%lld.5\n", ans / 2);
        else printf("%lld\n", ans / 2);
    }
}