[中譯] ProjectEuler 472 Comfortable Distance

看板puzzle (益智遊戲 - 數獨,拼圖,推理,西洋棋)作者tml (流刑人形)時間11年前 (2014/05/22 08:28)推噓2(2推 0噓 1→)

留言3則, 3人參與討論串1/1

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://www.ptt.cc/bbs/puzzle/M.1400718533.A.640.html