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=