【超初心者向け】AtCoderで最初に解くべき過去問集を分かりやすく解説します【８問目】

こんにちは！サトシです！

この記事では、「AtCoderに登録して最初に解くべき１０問（AtCoder Beginners Selection）」の８問目「Otoshidama」をめちゃくちゃ分かりやすく解説していきます。

AtCoder で問題を解くためには、新規登録しないといけません。

新規登録はこちらから → AtCoder に新規登録する

それでは、「Otoshidama」の解説をしていきます！

【競プロ】最初に解くべき過去問１０問をPythonで分かりやすく解説します！【AtCoder】こんにちは！サトシ（@satoshi365_blog）です！この記事では、「競技プログラミング（AtCoder）に登録し...

タップできる目次

８問目「Otoshidama」で身につくスキル
- exit(0) の使い方
８問目「Otoshidama」の解説
まとめ

８問目「Otoshidama」で身につくスキル

この問題では、こんなスキルが身につきます。

身につくスキル

exit(0) の使い方

先に、これがどのようなスキルなのかを説明します。

exit(0) の使い方

exit(0) を使うと、プログラムがそこで強制的に終わります。

例えば、下のように書きます。

print('Hello!') # Hello と出力される
exit(0)
print('Satoshi!') # 何も出力されない
print('Hello?') # 何も出力されない

８問目「Otoshidama」の解説

下の順番で解説していきます。

問題文
入力例と出力例
解答例
解説

それでは見ていきましょう。

問題文

問題文
日本でよく使われる紙幣は、10000 円札、5000 円札、1000 円札です。以下、「お札」とはこれらのみを指します。

青橋くんが言うには、彼が祖父から受け取ったお年玉袋にはお札が N 枚入っていて、合計で Y 円だったそうですが、嘘かもしれません。このような状況がありえるか判定し、ありうる場合はお年玉袋の中身の候補を一つ見つけてください。なお、彼の祖父は十分裕福であり、お年玉袋は十分大きかったものとします。

制約
・1 ≤ N ≤ 2000
・1000 ≤ Y ≤ 2 × 10⁷
・N は整数である。
・Y は 1000 の倍数である。

入力
入力は以下の形式で標準入力から与えられる。

N Y

出力
N 枚のお札の合計金額が Y 円となることがありえない場合は、’-1 -1 -1′ と出力せよ。

N 枚のお札の合計金額が Y 円となることがありうる場合は、そのような N 枚のお札の組み合わせの一例を「10000 円札 x 枚、5000 円札 y 枚、1000円札 z 枚」として、x、y、z を空白で区切って出力せよ。複数の可能性が考えられるときは、そのうちどれを出力してもよい。

ABC085C – Otoshidamaより引用

入力例と出力例

入力例

7 25000

出力例

2 0 5

7枚のお札が25000円である可能性があるかを調べます。

10000円が2枚、1000円が5枚のとき、25000円になるので、「2 0 5」と出力します。

解答例

n, y = map(int, input().split())
for m10000 in range(n + 1):
  for m5000 in range(n + 1 - m10000):
    m1000 = n - m10000 - m5000
    if m10000 * 10000 + m5000 * 5000 + m1000 * 1000 == y:
      print(m10000, m5000, m1000)
      exit(0)
print('-1 -1 -1')

解説

N = 7、Y = 25000 だったとします。この場合、下のように計算していきます。

10000円札が0枚、5000円札が0枚、1000円札が7枚のとき、合計25000円だったらプログラムを終了する
10000円札が0枚、5000円札が1枚、1000円札が6枚のとき、合計25000円だったらプログラムを終了する
10000円札が0枚、5000円札が2枚、1000円札が5枚のとき、合計25000円だったらプログラムを終了する
…
10000円札が7枚、5000円札が0枚、1000円札が0枚のとき、合計25000円だったらプログラムを終了する
合計25000円になることが1回もなかったら、「-1 -1 -1」を出力する

では、コードを詳しく解説していきます。

10000円の枚数を「m10000」
5000円の枚数を「m5000」
1000円の枚数を「m1000」

として解いていきます。

まずは、入力を受け取ります。

n, y = map(int, input().split())

for を使って、10000円札が0〜7枚ある場合を考えます。

for m5000 in range(n + 1 - m10000):

for を使って、5000円札が0〜7枚ある場合を考えます。

※10000円札が1枚あると考えているときは、5000円札が0〜6枚ある場合を考えます

  for m5000 in range(n + 1):

1000円札の枚数を考えます。

例えば、お札が合計7枚ある場合を考えます。10000円札が1枚、5000円札が2枚あるなら、1000円札は4枚あるはずです。

なので、下のように1000円札の枚数を求められます。

    m1000 = n - m10000 - m5000

もし合計金額が25000円だったら、それぞれのお札の枚数を出力して、プログラムを終了します。

    if m10000 * 10000 + m5000 * 5000 + m1000 * 1000 == y:
      print(m10000, m5000, m1000) exit(0)

「-1 -1 -1」と出力します。

※もし合計金額が25000円になることがあったら、すでにプログラムが終了しているはずなので、このプログラム「print(‘-1 -1 -1’)」は実行されません。

print('-1 -1 -1')

まとめとして、もう一度プログラムを確認してみましょう。

n, y = map(int, input().split())
for m10000 in range(n + 1):
  for m5000 in range(n + 1 - m10000):
    m1000 = n - m10000 - m5000
    if m10000 * 10000 + m5000 * 5000 + m1000 * 1000 == y:
      print(m10000, m5000, m1000)
      exit(0)
print('-1 -1 -1')

これで「N枚のお札で、合計Y円になる可能性があるか」を調べることができました。