グループで乗るリフト
締め切りが 2017/03/07 10:00 AM なので,その 1 分後に投稿されるように予約
設問
m 人のグループがスキー場でリフトやゴンドラに乗ろうとしています。
このスキー場には n 人乗りのリフトやゴンドラがあります。
グループでまとまって移動するため、連続したリフトやゴンドラに乗ることにします。
グループのメンバーは区別せず、各リフトやゴンドラに乗る人数だけを考えるとき、
1回の移動における乗り方が何通りあるかを求めてください。
ただし、誰も乗らないリフトやゴンドラはないものとします。
また、m, n ともに 32以下の正の整数とします。
例えば、m = 5, n = 3 のとき、以下の13パターンがあります。
パターン 1台目 2台目 3台目 4台目 5台目
(1) 1人 1人 1人 1人 1人
(2) 1人 1人 1人 2人 -
(3) 1人 1人 2人 1人 -
(4) 1人 2人 1人 1人 -
(5) 2人 1人 1人 1人 -
(6) 1人 1人 3人 - -
(7) 1人 3人 1人 - -
(8) 3人 1人 1人 - -
(9) 1人 2人 2人 - -
(10) 2人 1人 2人 - -
(11) 2人 2人 1人 - -
(12) 2人 3人 - - -
(13) 3人 2人 - - -
【入出力サンプル】
標準入力
5 3
標準出力
13
=====================
下図のような規則性を持った二次元数列になる
各列のオレンジの部分以降の桝目の数値は,それ以前の n 個の桝目の和(広義のフィボナッチ数列) n = 2(C 列)を見ればわかる
f = function(m, n) {
a = integer(m+1)
a[1] = 1
a[2:n] = 2^(0:(n-2))
for (i in n:m+1) {
a[i] = sum(a[i-n:1])
}
cat(a[m+1],"\n")
}
if (0) {
mn = scan(file("stdin", "r"))
f(mn[1], mn[2])
} else {
f(5, 3) # 13
f(6, 4) # 29
f(10, 2) # 89
f(25, 10) # 16646200
f(32, 16) # 2147205120
}
※コメント投稿者のブログIDはブログ作成者のみに通知されます