2021/11/10
C - Otoshidamaをpythonで解く
問題
今回解いた問題のリンクは↓
https://atcoder.jp/contests/abc085/tasks/abc085_c
整数N Yが与えられるので、10000 円札、5000 円札、1000 円札をN枚組み合わせて合計Y円になる組み合わせを出力せよというもの。
存在しない場合は -1 -1 -1を出力する。
解き方
愚直に全パターン洗い出して、あり得るものがあるか調べるだけで良さそう。
N, Y = map(int, input().split())
for x in range(N + 1):
for y in range(N + 1):
z = N - (x + y)
if 0 <= z <= 2000 and (10000 * x + 5000 * y + 1000 * z) == Y:
print(x,y,z)
exit()
else:
continue
print(-1,-1,-1)
ACしたもの↓
https://atcoder.jp/contests/abc085/submissions/26234787
余談
問題提出後に色々見ていると、O(1)で解くことも出来るらしい↓
https://ark4rk.hatenablog.com/entry/2018/01/08/201801
こういう発想できるようになりたい。