作者tml (流刑人形)
看板puzzle
標題[中譯] ProjectEuler 472 Comfortable Distance
時間Thu May 22 08:28:47 2014
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位數作為答案。
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 129.2.129.155
※ 文章網址: http://webptt.com/m.aspx?n=bbs/puzzle/M.1400718533.A.640.html
1F：推 jurian0101:貌似PE要出《社會疏離動力學導論》 05/22 11:41
2F：→ ignacio777:10^12... 05/22 12:22
3F：推 weijer0905:小便斗法則(? 05/22 16:35
※ 編輯: tml (129.2.129.155), 05/22/2014 23:56:43