DouKaku? 60 minke: 短くしてみた。 %= のところでハイラ...(コインを減らす払い方)

Comment detail

短くしてみた。
%= のところでハイライトがおかしくなるのが悲しい。

def pay(e, h)
  h.default = 0
  h.each {|c,n| e -= c*n }
  raise "Money!" if (e *= -1) < 0
  [500,100,50,10,5,1].each do |c|
    h[c] -= e/c
    e %= c
  end
  h.reject {|c,n| n <= 0}
end

おお、短い。すばらしい！
でも……

pay(147, {1=> 2, 5=>300, 10=> 4, 100=> 3})
=> {5=>299, 1=>2, 100=>2}

すいません、意地悪で（苦笑

pay(147, {1=> 2, 5=>300, 10=> 4, 100=> 3})
=> {5=>299, 1=>2, 100=>2}

これあってますよね。
たぶん#73の方と同じ疑問点なのだと思いますが、

5 * 299 + 1 * 2 + 100 * 2 = 1697
1697 - 147 = 1550

でおつりは500 * 3, 50 * 1。確かに一番減ります。こんなお金の出され方したら怒りますけど（笑

Pythonでも同じアルゴリズムで書いてみました。

from operator import *
def pay(m, w):
  r = dict()
  m = sum((k*w[k] for k in w)) - m
  if m < 0: raise "money"
  for c in (500,100,50,10,5,1):
    r[c] = w.get(c, 0) - m / c
    m %= c
  return dict(((k,v) for k,v in r.items() if v > 0))

なるほど、端的に言うと例えば100円支払う時に100円玉を101枚渡せば
「店員は最も枚数が少なくなる返し方でおつりを返す」という条件から
1万円札が返ってくるわけですね。

問題条件にそう書いてある以上、
結果がいくら常識に反していても
「100円玉を101枚出す」が正解です。

出題が甘かったですね～(^^;

「やりとりする枚数が最小になるように」という条件にすればよかったのかもしれませんね…。

DouKaku?

Comment detail

Index

Feed

Other

Link

Pathtraq