Edit

【pythonでABC180を解説】D - Takahashi Unevolved

問題概要

問題ページ

問題文

いろはちゃんはペットを育てるゲームにはまっています。

いろはちゃんはペットとして高橋君を飼っており、はじめ高橋君の 強さ は \(X\) 、経験値 は \(0\) です。
これらの値は次の \(2\) 種類の特訓によって増加します。

  • カコモンジムに通う:強さが \(A\) 倍になり、経験値は \(1\) 増える。
  • AtCoderジムに通う:強さが \(B\) 増え、経験値は \(1\) 増える。

高橋君は強さが \(Y\) 以上になると進化しますが、進化しない方がかわいいといろはちゃんは思っています。

そこで、強さが \(Y\) 以上にならないように高橋君に特訓を課すとき、経験値の最大値を求めてください。

制約

  • \(1 \leq X < Y \leq 10^{18}\)
  • \(2 \leq A \leq 10^9\)
  • \(1 \leq B \leq 10^9\)
  • 入力は全て整数

問題の考察

ACコード

import sys


def solve():
    readline = sys.stdin.buffer.readline
    mod = 10 ** 9 + 7
    x, y, a, b = list(map(int, readline().split()))
    mt = 0
    for i in range(10 ** 10):
        t = x * pow(a, i)
        if t < y:
            rest = y - t - 1
            mt = max(mt, i + rest // b)
        else:
            break
    print(mt)


if __name__ == '__main__':
    solve()

-Edit
-