# -*- coding: utf-8 -*-
# http://odz.sakura.ne.jp/projecteuler/index.php?cmd=read&page=Problem%2031
# 
# 各コインを 0 .. N 枚使ったときの組み合わせで
# 合計が200になる場合を数える．
# 
COINS = [1, 2, 5, 10, 20, 50, 100, 200].reverse
def dfs(sum, i)
  if (sum == 200)
    1
  elsif (i == COINS.size)
    0
  else
    # 合計が200を超えない回数だけCOINS[i]を使う
    (0 .. (200 - sum) / COINS[i]).reduce(0) {|s, j|
      # 次のコインで再起
      s + dfs(sum + COINS[i] * j, i + 1)
    }
  end
end
puts dfs(0, 0)