ProjectEuler 472 Comfortable Distance - 拼圖

472. Comfortable Distance II

http://projecteuler.net/problem=472

現有一排N個座位，並有N人遵循下述規則依序就座：

1. 所有人皆不相鄰。

2. 第一個人可以選擇任意座位。

3. 接下來每個人都在不違反規則1的前提下，選擇最遠離所有人的座位。如果有大於一個
　 座位符合條件，則選擇所有符合條件的座位中最左邊的那一個。

注意到因為規則1的關係，必然會有一些座位是自始至終沒人坐的，故有座位能坐的人必
然小於N（在N>1時）。

下圖是當N=15時所有可能的座位組合（數字代表就座順序）：

http://projecteuler.net/project/images/p472_n15.png

我們可以發現如果第一個人選的座位恰當，則有7個人能就座。

此時，第一個人有9個選擇使就座人數達到最大。

令f(N)為有N個座位時，第一個人有多少選擇使得就座人數最大。所以有f(1) = 1、
f(15) = 9、f(20) = 6以及f(500) = 16。

同時Σf(N) = 83為1≦N≦20時的和，Σf(N) = 13343為1≦N≦500時的和。

請求出Σf(N)在1≦N≦10^12時的和，並給出最後8位數作為答案。

--