#/***********************************************************
#    change.rb -- 小銭の払い方
#***********************************************************/

def change( n,  k )  # 再帰版 
    if (n < 0); return 0; end
    s = 1 + n / 5 + change(n - 10, 10)
    if (k >=  50); s += change(n -  50,  50); end
    if (k >= 100); s += change(n - 100, 100); end
    return s
end

def change1( n )  # 非再帰版 
    s = 0
    (n / 100).downto(0) do |i|     # 100円玉 
        t = n - 100 * i
        (t / 50).downto(0) do |j|   #  50円玉 
            u = t - 50 * j
            s += (1 + u / 5 - u / 10) * (1 + u / 10)
        end
    end
    return s
end

printf("お金の払い方\n")
printf("  金額    再帰版  非再帰版\n")
0.step(500, 5) do |i|
    printf("%6d  %8d  %8d\n", i, change(i, i), change1(i))
end

exit 0