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

[Leon (Achilles)]

※ 引述《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
推 RockLee:522808225 本身是回文 但它的平方不是回文
→ RockLee:不符合我所稱的 fair_root 的定義
→ Leon:my question is simple, based on you rule
→ Leon:how can I decide if the number I point out is or not?
推 RockLee:根據我的rule 522808225顯然不是 因為它不在我建的表中
→ Leon:then, how do you handle this case?
推 RockLee:既然我已經先建好表了 我只需檢查這個數在不在我的表中
→ RockLee:就知道它是不是 fair_root 了啊
推 ZanFu5566:不知道用0,1,2去建是否對所有N>0都成立呢
推 RockLee:第一篇推文中的用0,1,2去建的方法對N>1都成立
→ RockLee:(N=1的fair_root是1,2,3)
→ RockLee:以題目要求而言3^25~=8*10^11
→ RockLee:而我所提的方法實際檢查的candidates低於10^5
→ RockLee:故執行速度會更快 不過就這題而言並不一定需要這麼快就是