[中譯] ProjectEuler 328 Lowest-cost Search

[babufong (嗶嗶)]

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
推 utomaya:我可以算出來n=1->100 C(n)=17575了
→ utomaya:不過 到20000要跑8個小時耶 怎麼要那麼久?
→ utomaya:寫錯 20000要5分鐘~~ 200000要八個小時
→ babufong:這就是為何題目出來近7小時沒人解答出來的原因（？）
推 utomaya:應該是大家找不到1分鐘的解法吧
→ utomaya:應該是有1分鐘內的解法
→ utomaya:不過 我的電腦很慢 只有1.7GHz 換快一點的電腦應該可以
→ utomaya:3小時以內!
→ utomaya:如果跑耗時得程式的話 應該3小時以內就有第1個解答者才對?
推 KitWoolsey:好久沒玩這個了0.0
推 utomaya:跑了6小時 結果答案是錯的 而題目所給的hint數字我都符合
→ utomaya:終於知道這題難在哪了? 難怪現在為止沒人做出來
→ utomaya:而且我確定不是溢位的問題 應該是演算法有錯
→ utomaya:正確答案應該有12位數 而且比我的答案略小(26359....)
→ babufong:截至目前為止只有兩位做出來
推 LPH66:看來我在想的某個問題的答案應該是否定的了...
→ LPH66:果然這題不能單純 Divide & Conquer 呢
推 LPH66:也就是說大概只能用二維硬做  但這樣需要200K*200K的大表..
→ LPH66:以正解應是 12 位數來看 int 還不夠  要 long 的大小
→ LPH66:這等於是約 20G * 8 = 160G....= = 我再想想怎麼化簡好了
推 jurian0101:lol 已經四天了才17人算出來
推 jurian0101:請問因為worst case的條件較為優先，所以當N=11時"勝出
→ jurian0101:的應該是 4+6+8=18這個策略對吧。因此11是第一個必須
→ jurian0101:動用到三步猜測的N。
推 LPH66:三步猜測? 如果你是想說最多猜三次的話範例的 N=8 就是啦
推 LPH66:另外最多猜測次數的增加不是很穩定
→ LPH66:像 N=82 的最佳解最多是 11 次 (最多花費 305, 第一猜是 67)
→ LPH66:但 N=83 的最佳解最多只要 9 次 (最多花費310, 第一猜 68)
推 LPH66:有做的看要不要對一下小的答案...我的C(1000)=6753
→ LPH66:然後 \sum n=1~1000 C(n) = 3120345
→ LPH66:這個沒錯的話我就要來想想怎麼把這個大玩意搞小一點了
→ LPH66:(我目前的做法是 O(N^3)..這在N=二十萬時會久到我想殺人..)
→ alex2202:我也是求出 C(1000)=6753 能再提供大一點的測資嗎，感謝
→ jurian0101:也對啦，以讓一堆高手苦戰的題目來說divide&conquer
→ jurian0101:顯得太清純可愛了。仍不瞭問題出在哪 ~攤~
推 jurian0101:想到之前的最短加法練問題，也是OOXX裝清純。
推 utomaya:我也得出了sum n=1~1000 C(n) = 3120345
→ utomaya:不過Euler拒絕了我的答案!
推 utomaya:現在收斂到了260568268429 不過似乎還不是最佳解
→ utomaya:這大概是Euler有史以來最難的題目 比第289題還要難!
推 utomaya:解掉了 令人崩潰的題目!!
→ utomaya:sum n=1~1000 C(n) = 3120345 是正確的
→ utomaya:跑了16秒 果然是有一分鐘內的解法 記憶體也不需要太多
→ utomaya:之前錯的答案 開頭4碼竟是正確的!! 差了那麼一點
→ jurian0101:恭喜
→ utomaya:3秒鐘!! 不過論壇裡有人跑到0.25秒
→ utomaya:有人需要大一點的測資嗎? sum n=1~5000 C(n) = 103047288
→ utomaya:單看一個不準 要看總和才準...
→ utomaya:我之前錯的答案 C(5000)是對的 但C(4000)卻錯了
推 utomaya:0.046秒!!! 天啊~ 我比它還快了 現在是論壇裡最快的!
→ utomaya:可以跑到5億:C(5*10^8) 花了19分鐘又20秒
→ utomaya:但我的電腦很慢，如果用新型的電腦 應該可以6分鐘內