【ABC180 D】「Takahashi Unevolved」を解く【Python3】

コンテスト一覧へ

 

いろはちゃんが遊んでいるゲーム内のペットである高橋君は、はじめ「強さX、経験値0」です。

この値は2種類のジムに通うことにより増加するのですが、強さがY以上になると進化してしまいます。

進化させないようにジムに通わせたときの最大の経験値を求める問題です。

提出
x, y, a, b = map(int, input().split())
ans = 0

for i in range(10**18):
    if x*a>=x+b or x*a>=y:
        break
    x = x*a
    ans += 1

print(ans+(y-1-x)//b)

進化しないように経験値を多くするためには、強さの増加が少ないジムを選び続ける必要があります。

強さの増加は、それぞれ「×A」と「+B」です。

「×A」のほうは回数を重ねるごとに増加数が大きくなり、「+B」はずっと同じ増加数となります。

なので、「×A」の増加数が「+B」より小さいときは、「×A」を使い続け、「+B」を超えるところからは 「+B」のジムに通い続けることを考えます。

for文を用いて「×A」の回数を数え、増加数が「+B」以上になるか、Y以上になるかしたときにループを抜けます。

「+B」の回数は「(y-1-x)/b」の切り捨てで出すことができるので、最後にこれを足して出力します。

ちなみに、公式の解説ではfor文の代わりにwhile文を使っていました。

提出
x, y, a, b=map(int,input().split())
ans = 0

while a*x <= x+b and a*x < y:
    x *= a
    ans += 1

print(ans+(y-1-x)//b)

考え方は変わらないですね。

「a*x <= x+b and a*x < y」の条件を満たす間、同じ処理を繰り返します。

【ABC180】解説記事リスト

コンテスト一覧に戻る

コメントを残す

メールアドレスが公開されることはありません。