🎃
ABC 180 | D - Takahashi Unevolved
問題
考えたこと
どちらのジムも経験値は1づつ増えるので貪欲にカコモンジムかAtCoderジムか強さが増えにくいほうを選び続ければ最適解になる。愚直にどちらか選択する方法を選ぶとTLEする。よってよりよい解答を考える。
強さはカコモンジムはA倍、AtCoderジムはB増える。カコモンジムで増える分よりAtCoderジムで増えるほうが大きい間はカコモンジムに通い続け、それ以降はAtCoderに通い続ければよい。カコモンジムはA倍(Aは2以上)づつなので
コード
実装時のTips
- オーバーフローに気をつける
#include <bits/stdc++.h>
#include <atcoder/all>
using namespace std;
using namespace atcoder;
using ll = long long;
using ld = long double;
using uint = unsigned int;
using ull = unsigned long long;
const int MOD = 1e9 + 7;
int main() {
ull X, Y, A, B;
cin >> X >> Y >> A >> B;
ull exp = 0;
while (true) {
if ((ld) A * X < Y && A * X <= X + B) {
X *= A;
exp++;
} else {
break;
}
}
cout << exp + (Y - 1 - X) / B << endl;
}
Discussion