Re: [問題] 摳醬的第三題

看板Prob_Solve (計算數學 Problem Solving)作者 (Achilles)時間11年前 (2013/04/15 07:13), 編輯推噓5(509)
留言14則, 3人參與, 最新討論串3/4 (看更多)
※ 引述《RockLee (Now of all times)》之銘言: : ※ 引述《vocaloid (void *)》之銘言: : : https://code.google.com/codejam : : 參考答案好像還沒公佈 : : 請問第三題怎麼作比較有效率呢? : : large input 1 - 10 ^ 14 : : 2 - 10 ^ 100 : : 第一個我是跑測資前先建表 http://ideone.com/DDA2Sn : : 第二個本來想offline建但不知會跑多久... 10^30就花了3分鐘 : 假設我們定義 fair_root 為本身是回文且它的平方也是回文 : 我是先建到 15 位數的表觀察它的規律性 : 發現從 N = 4 位數開始 : 有可能的 candidates 只有 N - 2 位數的 fair_root 在頭尾第二位補 0 或 1 : 例如 N = 6 的 fair_root 為: : 100001 : 101101 : 110011 : 111111 : 200002 : 則 N = 8 的 fair_root 的 candidates 為: : 1 0 0000 0 1 : 1 0 0110 0 1 : 1 0 1001 0 1 : 1 0 1111 0 1 : 2 0 0000 0 2 : 1 1 0000 1 1 : 1 1 0110 1 1 : 1 1 1001 1 1 : 1 1 1111 1 1 : 2 1 0000 1 2 : 對這十個 candidates 實際驗算可發現 N = 8 的 fair_root 共九個: : 10000001 : 10011001 : 10100101 : 10111101 : 11000011 : 11011011 : 11100111 : 11111111 : 20000002 : 用這規律性去建表即使 online 建到 N = 50 的表也夠快 嗯.. 你確定嗎? 用 0,1,2 去造的好處是可以處理 進位 的狀況 但, 考慮一下這個數字 522808225 這個是用 5 當個位數造出來的. 請問你的規律性找的到這個數字嗎? 實際上, 就我所知, 這仍然是個 open problem. 這裡有解釋 necessay condition, 但是沒有給出 sufficient. http://arxiv.org/pdf/1210.7593v1.pdf 這個作者頗有名氣, 不過這篇還沒有 review 過 所以讀的時候自己要注意. -- ※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 142.136.125.30

04/15 07:40, , 1F
522808225 本身是回文 但它的平方不是回文
04/15 07:40, 1F

04/15 07:41, , 2F
不符合我所稱的 fair_root 的定義
04/15 07:41, 2F

04/15 07:53, , 3F
my question is simple, based on you rule
04/15 07:53, 3F

04/15 07:53, , 4F
how can I decide if the number I point out is or not?
04/15 07:53, 4F

04/15 08:05, , 5F
根據我的rule 522808225顯然不是 因為它不在我建的表中
04/15 08:05, 5F

04/15 08:10, , 6F
then, how do you handle this case?
04/15 08:10, 6F

04/15 08:24, , 7F
既然我已經先建好表了 我只需檢查這個數在不在我的表中
04/15 08:24, 7F

04/15 08:24, , 8F
就知道它是不是 fair_root 了啊
04/15 08:24, 8F

04/15 10:37, , 9F
不知道用0,1,2去建是否對所有N>0都成立呢
04/15 10:37, 9F

04/15 12:09, , 10F
第一篇推文中的用0,1,2去建的方法對N>1都成立
04/15 12:09, 10F

04/15 12:09, , 11F
(N=1的fair_root是1,2,3)
04/15 12:09, 11F

04/15 12:10, , 12F
以題目要求而言3^25~=8*10^11
04/15 12:10, 12F

04/15 12:10, , 13F
而我所提的方法實際檢查的candidates低於10^5
04/15 12:10, 13F

04/15 12:11, , 14F
故執行速度會更快 不過就這題而言並不一定需要這麼快就是
04/15 12:11, 14F
文章代碼(AID): #1HQpWIEP (Prob_Solve)
討論串 (同標題文章)
本文引述了以下文章的的內容:
以下文章回應了本文
完整討論串 (本文為第 3 之 4 篇):
文章代碼(AID): #1HQpWIEP (Prob_Solve)