裏 RjpWiki

Julia ときどき R, Python によるコンピュータプログラム,コンピュータ・サイエンス,統計学

切手の選び方は何通り?

2017年12月26日 | ブログラミング

切手の選び方は何通り?

締め切りが 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

コメント
  • X
  • Facebookでシェアする
  • はてなブックマークに追加する
  • LINEでシェアする

PVアクセスランキング にほんブログ村

PVアクセスランキング にほんブログ村