作者tml (流刑人形)
看板puzzle
标题[中译] ProjectEuler 444 The Roundtable Lotter
时间Sun Nov 10 08:07:04 2013
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
--
※ 发信站: 批踢踢实业坊(ptt.cc)
◆ From: 129.2.129.155
1F：推 LPH66:34 名入手 XD 结果前半截根本在唬人...(做完的就知道) 11/11 02:32
2F：→ LPH66:不过後半截是 Mathematica 硬上就是了 (死) 11/11 02:33
3F：→ tml:感觉给出E(111)是个满大的提示...这值这麽小就代表大部分情况 11/11 12:30
4F：→ tml:大家都在拚命换 11/11 12:30
5F：推 utomaya:第53位...前半比较简单 很容易就理解出最佳策略为何? 11/12 07:01
6F：→ utomaya:主要是卡在後半,这题真的是不简单...大家都好快 11/12 07:03
7F：→ utomaya:不过这游戏第一位player也满衰的 永远只能拿到一元 11/12 07:04
8F：推 LPH66:话说今天一次要出三题耶 @@ 据说是相关题所以一口气大放送 11/17 00:37