作者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/cn.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