競技プログラミング

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

プログラミング

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

 

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

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

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

 

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

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

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

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

身につくスキル
  • exit(0) の使い方

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

 

exit(0) の使い方

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

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

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

 

8問目「Otoshidama」の解説

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

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

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

 

問題文

 

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

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

制約
・1 ≤ N ≤ 2000
・1000 ≤ Y ≤ 2 × 107
・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 だったとします。この場合、下のように計算していきます。

  1. 10000円札が0枚、5000円札が0枚、1000円札が7枚のとき、合計25000円だったらプログラムを終了する
  2. 10000円札が0枚、5000円札が1枚、1000円札が6枚のとき、合計25000円だったらプログラムを終了する
  3. 10000円札が0枚、5000円札が2枚、1000円札が5枚のとき、合計25000円だったらプログラムを終了する
  4. 10000円札が7枚、5000円札が0枚、1000円札が0枚のとき、合計25000円だったらプログラムを終了する
  5. 合計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円になる可能性があるか」を調べることができました。

まとめ

もし分からない点などありましたら、気軽にTwitterやコメントなどでご質問ください^^

少しでも参考になれば嬉しいです!

COMMENT

メールアドレスが公開されることはありません。 * が付いている欄は必須項目です