pavlocat's diary

Twitter : @pavlocat

目指せお釣りマスター！(CodeIQ×はてな エンジニア夏祭り2013)

CodeIQ

 

 

この記事は、『CodeIQ×はてな エンジニア夏祭り2013(第2夜)』のお題その2『CodeIQの問題・パズルを考えよう！』へ参加するために作成されたものです。

 

 

※2013/10/1追記

入賞しました！

http://codeiq.hatenablog.com/entry/2013/09/06/150247

 

この問題はShort Coder Ozyさん(@ozy4dm)の手によってブラッシュアップされたものがCodeIQで出題されます。

 

※現在出題中です！(10/21 AM10時まで)

皆様のご応募をお待ちしております～(^-^)/

https://codeiq.jp/challenge.php?challenge_id=477

 

 

【問題】目指せお釣りマスター！

 

あなたは母親から買い物を頼まれ、10000円札1枚と、下記の買い物リストを渡されました。

 

商品1    ￥78
商品2    ￥295
商品3    ￥51
...
商品100  ￥39

 

（すべてを見るにはこちら）

 

あなたの母親はどうやらとてもマメな人で、全商品の値段を調べてくれたようです。

その一方で、100種類もまとめて買いに行かせるとは正気の沙汰ではないとあなたは怒りを覚えずにはいられませんでしたが、母親に頭の上がらないあなたはおとなしく従うことにしました。

 

 

さて、あなたは近所で唯一のスーパーマーケットに辿り着きました。

買い物リストの商品全てを一度に買えるお店はこの辺りではここしかありません。

しかし、このスーパーマーケットは一風変わった支払い方式を採用しており、なんと商品ごとに精算しなければなりません(笑)

どういうことかというと、あなたは100種類の商品を持ってレジに行くのですが、商品1の代金を支払う→お釣りをもらう→商品2の代金を支払う→お釣りをもらう...

と、商品ごとにお金を払う必要があるのです。

 

さらに残念なことに、レジを担当している若い兄ちゃんはバイトを始めたばかりのようで、特にお釣りを返すのがとても遅く、なんとお釣りを返すのに1枚1分もかかってしまいます^^;

 

こんな店で買い物してられるかとあなたは怒りを覚えずにはいられませんでしたが、この辺りにはこのスーパーマーケットしか無いので、あなたはおとなしくここで買い物をすることにしました。

 

しかしあなたもヒマではなく、帰ってから晩ご飯のお手伝いもしないといけませんし、ネトゲもやらないといけませんので、出来るだけ早く帰りたいと思っています。

この状況下において、あなたが出来ることと言えば、もらうお釣りが最小になるように渡すお金を工夫することくらいです（そういうことにしておいてください）。

 

そこで問題です。(2種類あります)

 

問題1

買い物リストに書かれている順番で商品の精算を行うとき、レジ係がお釣りを返すのにかかる時間が最小になるようなお金の渡し方を考えてください。

 

　例：100円玉1枚と、以下の買い物リストを渡されたとき

商品1    ￥16
商品2    ￥54

　　

　　①商品1(16円)の精算

　　　100円(100円玉x1)を渡し、84円(50円玉x1、10円玉x3、1円玉x4)をもらう

　　　8枚お釣りをもらうので、8分かかる。

　　②商品2(54円)の精算

　　　54円(50円玉x1、1円玉x4)を渡す。

　　　ちょうど払えたので、お釣りはなし。

 

　　上記の例だと、合計で8分かかったことになります。

 

問題2

　レジ係がお釣りを返すのにかかる時間が最小になるよう、商品を渡す順番と、お金の渡し方を考えてください。

 

　例：100円玉1枚と、以下の買い物リストを渡されたとき

商品1    ￥16
商品2    ￥54

　　

　　問題1では商品1→商品2の順で精算をしましたが、商品2→商品1の順で精算をする場合の例を見てみましょう。

　　①商品2(54円)の精算

　　　100円(100円玉x1)を渡し、46円(10円玉x4、5円玉x1、1円玉x1)をもらう

　　　6枚お釣りをもらうので、6分かかる。

　　②商品1(16円)の精算

　　　16円(10円玉x1、5円玉x1、1円玉x1)を渡す。

　　　ちょうど払えたので、お釣りはなし。

 

　　上記の例だと、合計で6分かかったことになり、問題1の例よりも時間を短縮できたことになります。

 

解答方法(問題1/2共通)

　解答は、各商品名と、その商品の精算が終了した後のお財布の状態を1行で表してください。

　1行ごとの形式は「商品名,10000円札(の枚数・以下略),5000円札,1000円札,500円玉,100円玉,50円玉,10円玉,5円玉,1円玉」とします。

 

　例：問題1で例示した解答を提出するとき

商品1,0,0,0,0,0,1,3,0,4
商品2,0,0,0,0,0,0,3,0,0

　

　　※問題1の解答を提出するとき、ファイル名は「answer1.txt」としてください。

　

　例：問題2で例示した解答を提出するとき

商品2,0,0,0,0,0,0,4,1,1
商品1,0,0,0,0,0,0,3,0,0

　　※問題2の解答を提出するとき、ファイル名は「answer2.txt」としてください。

 

　なお、101行目以降は自由に使っていただいて構いません(結城先生方式です(笑))。

　感想や、使用した言語、プログラム等何でもご自由にお書きください。

　(なお、プログラムを書くとわたしの勉強になりとても嬉しいです(笑))

 

採点方法(問題1/2共通)

　採点は各商品を精算した後にもらったお釣りの枚数を合計し、小さければ小さいほど高得点とします。

　問題1の例では8枚が、問題2の例では6枚が最高得点となります。

　※正しく精算できていない(計算が合わない)部分があった場合や、解答形式のミスがあった場合、採点はいたしかねます。（文字コードは気にしなくて良いです）

 

備考

  • 使えるお金は母親から渡された10000円のみです。
  • 買い物リストの商品の合計金額は10000円以下です。
  • お釣りが切れることは無く、レジ係は常に最適なお釣りの渡し方をする（渡す枚数が最小となるようにする）ものとします。
  • 解答の提出は、問題1/2のどちらか一方のみでも構いません。