ProjectEuler 444 The Roundtable Lotter - 拼圖

444. The Roundtable Lottery

http://projecteuler.net/problem=444

有p個人圍在一圓桌前進行交換刮刮樂的遊戲。遊戲一開始每個人都會拿到一張刮刮樂，

其面額為不重複的1到p元。每個人的遊戲目的是要在離開遊戲時有最高的獎金。


首先亂數選定一個玩家作為開始，沿著圓桌依序進行遊戲，輪到一個玩家時，他可以有

以下兩種選擇：

　‧刮開他的那張刮刮樂並將其面額展示給所有其他玩家看。

　‧把他的刮刮樂和前面已經刮開的任一玩家交換，然後拿著那張已經刮過的刮刮樂離

　　開遊戲。刮刮樂被換掉的玩家則將新到手的那張刮開並展示其面額給所有在場玩家。

當每張刮刮樂都被刮開則遊戲結束，還在場的玩家只能離開並兌現自己手頭的刮刮樂。

假設每個玩家都選擇了兌現期望值最高的策略。


令E(p)代表由p個玩家開始的情況下，遊戲結束時才離開的玩家的人數的期望值。

（例如：E(111) = 5.2912當四捨五入到五位有效位數。）

N
令S (N) = Σ E(p)
1 p=1

N
令S (N) = Σ S (p)，對所有k > 1。
k p=1 k-1

請求出S (10^14)並用科學記號給出答案至10位有效位數。以小寫e作為真數與首數的
20

分隔（例如S (100) = 5.983679014e5）。
3

--