ソースコードをジャッジにかけた時、一件のみWAが出てしまいます。
このソースコードにおいて、どのような状況下でWAが出るのでしょうか?
問題内容
https://atcoder.jp/contests/abc074/tasks/arc083_a
すぬけ君はビーカーに砂糖水を作ろうとしています。 最初ビーカーは空です。すぬけ君は以下の
4種類の操作をそれぞれ何回でも行うことができます。一度も行わない操作があっても構いません。・操作 1: ビーカーに水を 100A[g] 入れる。
・操作 2: ビーカーに水を 100B[g] 入れる。
・操作 3: ビーカーに砂糖を C[g] 入れる。
・操作 4: ビーカーに砂糖を D[g] 入れる。すぬけ君の実験環境下では、水 100[g] あたり砂糖は E[g] 溶けます。
すぬけ君はできるだけ濃度の高い砂糖水を作りたいと考えています。
ビーカーに入れられる物質の質量 (水の質量と砂糖の質量の合計) が F[g] 以下であり、 ビーカーの中に砂糖を溶け残らせてはいけないとき、
すぬけ君が作る砂糖水の質量と、それに溶けている砂糖の質量を求めてください。 答えが複数ある場合はどれを答えても構いません。水 a[g] と砂糖 b [g] を混ぜた砂糖水の濃度は 100ba+b [%]です。 また、この問題では、砂糖が全く溶けていない水も濃度0 [%] の砂糖水と考えることにします。
回答方針
大まかには以下の流れでソースコードを記述しました。
- 水の取り得るパターンを列挙
- 砂糖の取り得るパターンを列挙
- 水と砂糖の組み合わせを全検証し、最大濃度の組み合わせを探す
ソースコード
def concentration(water, suger):
return 100 * suger / (water + suger)
WATER_A, WATER_B, SUGER_C, SUGER_D, MELT_PER_100, LIMIT = map(int, input().split())
WATER_A *= 100
WATER_B *= 100
# 砂糖の溶解率の上限
MELT_PERCENT_LIMIT = concentration(100, MELT_PER_100)
wa = wb = sc = sd = 0
water_set = set()
while wa * WATER_A <= LIMIT:
while wb * WATER_B <= LIMIT:
water = wa * WATER_A + wb * WATER_B
if water <= LIMIT:
water_set.add(water)
wb += 1
wb = 0
wa += 1
suger_set = set()
while sc * SUGER_C <= LIMIT:
while sd * SUGER_D <= LIMIT:
suger = sc * SUGER_C + sd * SUGER_D
if suger <= LIMIT:
suger_set.add(suger)
sd += 1
sd = 0
sc += 1
ans_suger_water = 0
ans_suger = 0
# 最大溶解率を保持するための変数
max_concentration = 0
for water in water_set:
for suger in suger_set:
# 砂糖水の量が0より大きく制限量以下以外の場合は次のループへ
if not (0 < water + suger <= LIMIT):
continue
# 砂糖濃度計算
suger_precent = concentration(water, suger)
# 砂糖濃度が最高を更新かつ限界濃度を超えていなければ答えを更新
if max_concentration < suger_precent <= MELT_PERCENT_LIMIT:
max_concentration = suger_precent
ans_suger_water = water + suger
ans_suger = suger
print(ans_suger_water, ans_suger)