切手の選び方は何通り？
締め切りが 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
