TLEの対処法がわからない

Question

Atcoderの問題にチャレンジしているのですがTLEとなってしまい、その解決策が思い浮かびません。どなたかご教授いただきたいです。
問題は
水色のボールが A 個容器に入っています。高橋くんはこの容器に対し、以下の操作を 0 回以上好きなだけ繰り返します。

水色のボール B 個と赤色のボール C 個を容器に追加する。
高橋くんの目標は、容器に入っている水色のボールの個数が赤色のボールの個数の D 倍以下になるようにすることです。

目標が達成可能かを判定し、可能なら必要な操作回数の最小値を求めてください。
制約
1≤A,B,C,D≤10^5
入力は全て整数である。

コードは以下のようです。

A,B,C,D = map(int,input().split())
x = 0
if B > C*D:
    print(-1)
    exit()
while True:
    if A+B*x <= C*x*D:
        print(x)
        break
    else:
        x += 1

Comments

[maisumakun]

問題はどのようなものでしょうか？

Answer 1

まずは、紙と鉛筆で方程式を立ててみましょう。

ループを使った力技で割り出さなくても、この問題の答えは算出できます。

Answer 2

A, B, C, D の値によっては、x をいくら増やしても A+Bx <= Cx*D が成立しないことがあります。
その場合、ループは終わりません。
たとえば A = 1, B = 10, C = 1, D = 1 の場合、これが成立する正の x はありません。
たとえば A = 10, B = 1, C = 1, D = 1 の場合、これが成立する正の x はありません。

Comments

[majiponi]

B=CDの場合以外は、謎のループの前に弾かれるのでは?

[Zuishin]

本当ですね。数値を書き直します。

[mai_yoko]

B=CDの場合が抜けていました。わかりやすい説明ありがとうございました！