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); } }