切手の選び方は何通り？

切手の選び方は何通り？

締め切りが 2017/12/26 10:00 AM なので，その 1 分後に投稿されるように予約

設問

現在、普通切手は以下の19種類の金額が発売されています。
[1, 2, 3, 5, 10, 20, 30, 50, 62, 82, 92, 100, 120, 140, 205, 280, 310, 500, 1000]
※それぞれ、単位は円
（参考：日本郵便）

これらの切手をそれぞれ1枚ずつ持っているとき、ある金額を作る切手の選び方が何通りあるかを求めます。
※同じ金額でデザインが異なる切手はありますが、一つの金額に対して1枚ずつ持っているものとします。

例えば、70円を貼りたい場合、以下の5通りがあります。
(1) 62 + 5 + 3
(2) 62 + 5 + 2 + 1
(3) 50 + 20
(4) 50 + 10 + 5 + 3 + 2
(5) 30 + 20 + 10 + 5 + 3 + 2

標準入力から貼りたい金額が与えられたとき、その切手の選び方が何通りあるかを求め、標準出力に出力してください。
なお、入力される金額は3012円以下の正の整数とします。

【入出力サンプル】
標準入力
70

標準出力
5

====================

この問題は，R で制限時間内に解けた。bincombinations の再掲を除けば，簡単至極。

f = function(n) {
  bincombinations = function (p) {
    retval = matrix(0, nrow = 2 ^ p, ncol = p)
    for (n in 1:p) {
      retval[, n] = rep(c(rep(0, (2 ^ p / 2 ^ n)), rep(1, (2 ^ p / 2 ^ n))),
                        length = 2 ^ p)
    }
    retval
  }
  a = bincombinations(19)
  b = c(1,2,3,5,10,20,30,50,62,82,92,100,120,140,205,280,310,500,1000)
  x = a %*% b
  cat(sum(x == n))
}

# f(scan(file("stdin", "r")))

f(70) # 5
f(100) # 11
f(543) # 144
f(1234) # 240
f(3000) # 1

system.time(f(100)) # 0.103 s

Python3 だと，f(100) が 3.470 s で，とんでもなく遅い。

import numpy as np
import itertools as it

def f(n):
    a = list(it.product([0, 1], repeat=19))
    b = [1,2,3,5,10,20,30,50,62,82,92,100,120,140,205,280,310,500,1000]
    x = np.dot(a, b)
    print(sum(x==n))

f(70) # 5
f(100) # 11
f(543) # 144
f(1234) # 240
f(3000) # 1

import time
a = time.time(); f(100); time.time()-a # 3.470 s