ICPC 2019 Asia Yokohama Regional A Fast Forwarding
問題ページ
速度を何回も上げ下げする必要はない.したがって1,3,9,27,9,9,3,3,1のように一回上げて下げるような変化を考えればよい.時間を短くするには,貪欲にできるだけ早い速度にするべきである.
- 速度を上げられる 秒で目標の時間を過ぎない
- 速度を維持できる 秒で目標の時間を過ぎない
- これ以外 → を3で割る
のどれかにしたがって速度を変更する.
#include <bits/stdc++.h> using namespace std; using ll = long long int; #define FOR(i, a, n) for (ll i = (ll)a; i < (ll)n; ++i) #define REP(i, n) FOR(i, 0, n) struct FastIO {FastIO() { cin.tie(0); ios::sync_with_stdio(0); }}fastiofastio; signed main() { ll t; cin >> t; if(t == 0) { cout << 0 << endl; return 0; } ll speed = 1, sum = 1, ans = 1; while(sum<t) { // speedを上げるか? { ll need = (speed*9-1)/2; if(sum+need <= t+1) speed *= 3; } // speedを維持できるか? { ll need = (speed*3-1)/2; if(sum+need > t+1) speed /= 3; } sum += speed; ans++; } cout << ans << endl; }