coins = [5,3,1]
maxcoin = coins.first
base = [0]
diff = 0
until diff == maxcoin
number = base.length
min = 1000000
found = false
for c in coins
num = number - c
if num < 0
next
end
dist = 1 + base[num]
if !found || dist < min
found = true
min = dist
end
end
base << min
if number >= 2 * maxcoin
sumhi = base[-maxcoin, maxcoin].reduce(:+)
sumlo = base[-maxcoin - maxcoin, maxcoin].reduce(:+)
diff = sumhi - sumlo
end
end
#File.open(ARGV[0]).each_line do |line|
for number in 10000 .. 10009
#number = line.to_i
init = 0;
if number >= base.length
init = 1 + (number - base.length) / maxcoin
end
coins = init + base[number - init * maxcoin]
puts "#{number} -> #{coins}"
end
Y29pbnMgPSBbNSwzLDFdCm1heGNvaW4gPSBjb2lucy5maXJzdApiYXNlID0gWzBdCmRpZmYgPSAwCgp1bnRpbCBkaWZmID09IG1heGNvaW4KICAgIG51bWJlciA9IGJhc2UubGVuZ3RoCiAgICBtaW4gPSAxMDAwMDAwCiAgICBmb3VuZCA9IGZhbHNlCiAgICBmb3IgYyBpbiBjb2lucwogICAgICAgIG51bSA9IG51bWJlciAtIGMKICAgICAgICBpZiBudW0gPCAwCiAgICAgICAgICAgIG5leHQKICAgICAgICBlbmQKICAgICAgICBkaXN0ID0gMSArIGJhc2VbbnVtXQogICAgICAgIGlmICFmb3VuZCB8fCBkaXN0IDwgbWluCiAgICAgICAgICAgIGZvdW5kID0gdHJ1ZQogICAgICAgICAgICBtaW4gPSBkaXN0CiAgICAgICAgZW5kCiAgICBlbmQKICAgIGJhc2UgPDwgbWluCgogICAgaWYgbnVtYmVyID49IDIgKiBtYXhjb2luCiAgICAgICAgc3VtaGkgPSBiYXNlWy1tYXhjb2luLCBtYXhjb2luXS5yZWR1Y2UoOispCiAgICAgICAgc3VtbG8gPSBiYXNlWy1tYXhjb2luIC0gbWF4Y29pbiwgbWF4Y29pbl0ucmVkdWNlKDorKQogICAgICAgIGRpZmYgPSBzdW1oaSAtIHN1bWxvCiAgICBlbmQKZW5kCgoKCiNGaWxlLm9wZW4oQVJHVlswXSkuZWFjaF9saW5lIGRvIHxsaW5lfApmb3IgbnVtYmVyIGluIDEwMDAwIC4uIDEwMDA5CiAgI251bWJlciA9IGxpbmUudG9faQogIGluaXQgPSAwOwogIGlmIG51bWJlciA+PSBiYXNlLmxlbmd0aAogICAgICBpbml0ID0gMSArIChudW1iZXIgLSBiYXNlLmxlbmd0aCkgLyBtYXhjb2luCiAgZW5kCiAgY29pbnMgPSBpbml0ICsgYmFzZVtudW1iZXIgLSBpbml0ICogbWF4Y29pbl0KICBwdXRzICIje251bWJlcn0gLT4gI3tjb2luc30iCmVuZAo=