トップページに戻る    次のC#のサンプルへ    前のC#のサンプルへ

Problem472 気楽な距離2

問題

N 個の一列に並んだ座席がある. N 人の人たちが以下のルールに従って次々に座席を埋めていく:

1.隣には誰も座っていないこと.
2.最初の人はどの座席を選んでも良い.
3.次の人はそれぞれにすでに座った人の座席からルール1に違反しない限りで最も離れた座席を選ぶ.
  条件を満たす選択が一つ以上ある場合は, 最左の座席を選ぶ.

ルール1により, 座席のいくつかは確実に空いたままとなり,
座席に座ることのできる最大人員は N 未満となる (N > 1 のとき).

N=15 の時に可能な席順は以下の通り:



最初の人が正しく選択すれば, 15個の座席なら7人が座れることがわかる.
また最初の人は座れる人数を最大にする選択肢を9つ持っていることがわかる.

一列に並んだN個の座席に対し
最初の人が座席に座れる人数を最大にできる選択肢の数をf(N)としよう.

f(15) = 9, f(20) = 6, そして f(500) = 16.

また,  1 <= N <=  20 に対し シグマ(f(N)) =    83
そして 1 <= N <= 500 に対し シグマ(f(N)) = 13343

1 <= N <= 1兆 における シグマ(f(N)) を求めよ. 回答として末尾8桁を答えよ.


ソース



実行結果



解説