金額支払い方法

締め切りが 12/30 10:00 AM なので，その 1 分後に公開されるように予約登録

問題:パスカルの三角形，それぞれの値を「金額(日本円)」だと考えることにします。
例えば、「1」は1円、「2」は2円、「10」は10円です。
このとき、n段目のそれぞれの値について、お札や硬貨での最小の枚数を考え、その枚数の和を求めることにします。

例えば、n=4のとき、1, 4, 6, 4, 1の並びでは、1円＝1枚、4円＝4枚、6円＝2枚(5円玉＋1円玉)なので、
すべて足すと12枚になります。
同様に、n=9のとき、すべて足すと48枚になります。

標準入力からnの値が与えられたとき、その枚数の和を標準出力に出力するプログラムを作成してください。
なお、使える硬貨、お札は1円玉、5円玉、10円玉、50円玉、100円玉、500円玉、1000円札、2000円札、5000円札、10000円札です。
（※nの値は最大で50までとします。）

解答例: R だと，簡単だ。

con = file("stdin", "r")
n = as.integer(readLines(con, 1))
t = choose(n, 0:n)
f = function(x) {
    count = 0
    for (m in c(10000, 5000, 2000, 1000, 500, 100, 50, 10, 5, 1)) {
        count = count + x %/% m
        x = x %% m
    }
    count
}
options(digits=16)    
cat(sum(sapply(t, f)))