作者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