中野's workspace

  • Profile
  • Privacy
  • Contact

2021/11/10

C - Otoshidamaをpythonで解く

  • #atcoder

目次

問題

今回解いた問題のリンクは↓
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

こういう発想できるようになりたい。

このエントリーをはてなブックマークに追加
  • Copyright © 2019. Makoto Nakano
  • ALL Tags