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

問題概要

問題ページ

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()