ABC195 B問題 Many Orangesを解く

みかん

ABC195のB問題を振り返りつつ解説します。

AグラムからBグラムの重さのみかんがあって、何個か選んでちょうどWキログラムになった時に、最大の個数と最小の個数を求める問題です。

atcoder.jp

みかんの重さは整数とは限らないとか書いてあって、頭の中に無限に細かく刻まれた数直線が浮かび、いったん飛ばしてC問題に着手しました。
よくよく読むと、何個選ぶかは全探索できるんですね。
Wはキログラムという親切設定なので、みかんの重さの最小値は1グラムですし、Wの最大は1000、キログラムなのでグラム換算して、個数は最大でです。
重さを個数で割った時にAとBの範囲に収まっていれば、条件を満たした個数になるので、その数を配列に記録します。

条件を満たした個数が保存されている配列の中の最大値と最小値が答えです。
配列に何もなければ、'UNSATISFIABLE'と出力します。

A, B, W = list(map(int, input().split()))
W *= 1000

ans_num = []
for i in range(1, 10**6 + 1):
    if A <= W/i <= B:
        ans_num.append(i)
if ans_num:
    print(min(ans_num), max(ans_num))
    exit()
print('UNSATISFIABLE')

全探索する発想に至るの難しかったな。。。