AtCoder ABC 195 B – Many Oranges Python解説

スポンサーリンク

Many Oranges

みかんがたくさんあります。どのみかんの重さも A グラム以上 B グラム以下であることがわかっています。(みかんの重さは整数とは限りません。)
この中からいくつかのみかんを選んだところ、選んだみかんの重さの合計がちょうど W キログラムになりました。
選んだみかんの個数として考えられる最小値と最大値を求めてください。ただし、このようなことが起こり得ないなら、かわりにそのことを報告してください。

AtCoder Beginner Contest 「Many Oranges」

みかんの重さはAグラム以上Bグラム以下なので、A * みかんの個数(N) <= W <= B * みかんの個数(N)という条件式が成り立てばWキログラムにすることができます。

Wキログラムにならない例として入力例を見てみます。みかんの重さが300グラム以上333グラム以下のとき、1000グラムにすることができるか?
この場合、みかんを3個選んだら、900グラム以上999グラム以下になります。みかん4個を選ぶと、1200グラム以上1332グラム以下となり、A * みかんの個数 <= W <= B * みかんの個数を満たさないので、どのみかんを選んでもWキログラムにすることはできません。

ですので、A * みかんの個数 <= W <= B * みかんの個数を満たす場合のみかんの個数の最大値、最小値を調べていきます。

a, b, w = map(int, input().split())
w = 1000 * w

max_ans = 0
min_ans = 1000000

for i in range(1, w + 1):
    if a * i <= w <= b * i:
        max_ans = max(max_ans, i)
        min_ans = min(min_ans, i)
        
if max_ans == 0:
    print("UNSATISFIABLE")
else:
    print(min_ans, max_ans)

まずはwを扱いやすいようにグラムに変換しています。for文では条件文a * i <= w <= b * iを満たすか判定し、条件を満たしたら、max関数、min関数でみかんの個数の最大値、最小値を求めています。条件を満たすみかんがなければ、max_ans == 0で判定しUNSATISFIABLEを出力、条件を満たすみかんがあれば最小値、最大値を出力して完了です。

AtCoderB問題

Posted by cheese