作者babufong (哔哔)
看板puzzle
标题[中译] ProjectEuler 328 Lowest-cost Search
时间Sun Mar 13 12:32:35 2011
328. Lowest-cost Search
http://projecteuler.net/index.php?section=problems&id=328
我们要尝试用猜数字的方法找出一个从{1, 2,......, n}的集合中挑出来的某数
我们猜的每个数字会花费将与我们所猜的数字相同，然而我们可能得到三种情况：
‧你猜的数字比我所选的还要低 或是
‧哇！一模一样！ 或是
‧你猜的数字比我所选的还要高
给定一个 n，我们要考虑最佳的策略，也就是考虑在该策略中总和最高，但是所有策略中
总和最小的。
如果 n = 3，最佳策略就是我们猜 2，这样答案就呼之欲出了，我们花费了 2。
如果 n = 8，我们可能想要一次砍半地猜，於是乎我们可能猜 4，如果某数比 4 大
我们就可能还要额外的一或两次猜测，第二次我们猜 6，如果某数仍比 6 大
那某数就是 7 或 8，我们第三次就猜 7，最後的花费就是 4 + 6 + 7 =
17
但我们可以发现当 n = 8 时，5 才是最佳选择。当某数比 5 大，我们只要猜 7 就有答案
然而我们花费 5 + 7 =
12。
如果某数比 5 小，我们第二次会猜 3，如果又比 3 还要小，我们就猜 1，这样答案就一
定会出来，而总和是 5 + 3 + 1 =
9。
所以在 n = 8 且我们采取第一次猜 5 的策略中的所有情况，总和最多的是 12，但他比起
前一个策略总和 17 还要好，所以这才是 n = 8 的最佳策略。
使 C(n) 为 n 的最佳策略中花费最多的，就像上面所说。
因此 C(1) = 0, C(2) = 1, C(3) = 2, C(8) = 12。
100
同样的，C(100) = 400 且 ΣC(n) = 17575
n=1
200000
请找出 Σ C(n)。
n=1
--
※ 发信站: 批踢踢实业坊(ptt.cc)
◆ From: 125.224.1.227
1F：推 utomaya:我可以算出来n=1->100 C(n)=17575了 03/13 12:49
2F：→ utomaya:不过 到20000要跑8个小时耶 怎麽要那麽久? 03/13 12:50
3F：→ utomaya:写错 20000要5分钟~~ 200000要八个小时 03/13 12:52
4F：→ babufong:这就是为何题目出来近7小时没人解答出来的原因（？） 03/13 12:53
5F：推 utomaya:应该是大家找不到1分钟的解法吧 03/13 12:57
6F：→ utomaya:应该是有1分钟内的解法 03/13 12:57
7F：→ utomaya:不过 我的电脑很慢 只有1.7GHz 换快一点的电脑应该可以 03/13 12:58
8F：→ utomaya:3小时以内! 03/13 12:58
9F：→ utomaya:如果跑耗时得程式的话 应该3小时以内就有第1个解答者才对? 03/13 13:00
10F：推 KitWoolsey:好久没玩这个了0.0 03/13 13:26
11F：推 utomaya:跑了6小时 结果答案是错的 而题目所给的hint数字我都符合 03/13 19:23
12F：→ utomaya:终於知道这题难在哪了? 难怪现在为止没人做出来 03/13 19:24
13F：→ utomaya:而且我确定不是溢位的问题 应该是演算法有错 03/13 19:25
14F：→ utomaya:正确答案应该有12位数 而且比我的答案略小(26359....) 03/13 19:28
15F：→ babufong:截至目前为止只有两位做出来 03/14 02:44
16F：推 LPH66:看来我在想的某个问题的答案应该是否定的了... 03/14 02:44
17F：→ LPH66:果然这题不能单纯 Divide & Conquer 呢 03/14 02:45
18F：推 LPH66:也就是说大概只能用二维硬做 但这样需要200K*200K的大表.. 03/14 02:55
19F：→ LPH66:以正解应是 12 位数来看 int 还不够 要 long 的大小 03/14 02:56
20F：→ LPH66:这等於是约 20G * 8 = 160G....= = 我再想想怎麽化简好了 03/14 02:56
21F：推 jurian0101:lol 已经四天了才17人算出来 03/16 21:44
22F：推 jurian0101:请问因为worst case的条件较为优先，所以当N=11时"胜出 03/16 23:32
23F：→ jurian0101:的应该是 4+6+8=18这个策略对吧。因此11是第一个必须 03/16 23:33
24F：→ jurian0101:动用到三步猜测的N。 03/16 23:33
25F：推 LPH66:三步猜测? 如果你是想说最多猜三次的话范例的 N=8 就是啦 03/17 09:46
26F：推 LPH66:另外最多猜测次数的增加不是很稳定 03/17 09:53
27F：→ LPH66:像 N=82 的最佳解最多是 11 次 (最多花费 305, 第一猜是 67) 03/17 09:54
28F：→ LPH66:但 N=83 的最佳解最多只要 9 次 (最多花费310, 第一猜 68) 03/17 09:54
29F：推 LPH66:有做的看要不要对一下小的答案...我的C(1000)=6753 03/17 10:02
30F：→ LPH66:然後 \sum n=1~1000 C(n) = 3120345 03/17 10:02
31F：→ LPH66:这个没错的话我就要来想想怎麽把这个大玩意搞小一点了 03/17 10:02
32F：→ LPH66:(我目前的做法是 O(N^3)..这在N=二十万时会久到我想杀人..) 03/17 10:03
33F：→ alex2202:我也是求出 C(1000)=6753 能再提供大一点的测资吗，感谢 03/17 13:47
34F：→ jurian0101:也对啦，以让一堆高手苦战的题目来说divide&conquer 03/17 15:37
35F：→ jurian0101:显得太清纯可爱了。仍不了问题出在哪 ~摊~ 03/17 15:38
36F：推 jurian0101:想到之前的最短加法练问题，也是OOXX装清纯。 03/18 17:37
37F：推 utomaya:我也得出了sum n=1~1000 C(n) = 3120345 03/19 13:58
38F：→ utomaya:不过Euler拒绝了我的答案! 03/19 13:59
39F：推 utomaya:现在收敛到了260568268429 不过似乎还不是最佳解 03/19 14:03
40F：→ utomaya:这大概是Euler有史以来最难的题目 比第289题还要难! 03/19 14:29
41F：推 utomaya:解掉了 令人崩溃的题目!! 03/19 23:58
42F：→ utomaya:sum n=1~1000 C(n) = 3120345 是正确的 03/19 23:59
43F：→ utomaya:跑了16秒 果然是有一分钟内的解法 记忆体也不需要太多 03/20 00:04
44F：→ utomaya:之前错的答案 开头4码竟是正确的!! 差了那麽一点 03/20 00:09
45F：→ jurian0101:恭喜 03/20 02:05
46F：→ utomaya:3秒钟!! 不过论坛里有人跑到0.25秒 03/24 20:14
47F：→ utomaya:有人需要大一点的测资吗? sum n=1~5000 C(n) = 103047288 03/24 20:15
48F：→ utomaya:单看一个不准 要看总和才准... 03/24 20:15
49F：→ utomaya:我之前错的答案 C(5000)是对的 但C(4000)却错了 03/24 20:16
50F：推 utomaya:0.046秒!!! 天啊~ 我比它还快了 现在是论坛里最快的! 03/31 00:43
51F：→ utomaya:可以跑到5亿:C(5*10^8) 花了19分钟又20秒 03/31 00:44
52F：→ utomaya:但我的电脑很慢，如果用新型的电脑 应该可以6分钟内 03/31 00:45