作者Leon (Achilles)
站內Prob_Solve
標題Re: [問題] 摳醬的第三題
時間Mon Apr 15 07:13:19 2013
※ 引述《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
1F：推 RockLee:522808225 本身是回文 但它的平方不是回文 04/15 07:40
2F：→ RockLee:不符合我所稱的 fair_root 的定義 04/15 07:41
3F：→ Leon:my question is simple, based on you rule 04/15 07:53
4F：→ Leon:how can I decide if the number I point out is or not? 04/15 07:53
5F：推 RockLee:根據我的rule 522808225顯然不是 因為它不在我建的表中 04/15 08:05
6F：→ Leon:then, how do you handle this case? 04/15 08:10
7F：推 RockLee:既然我已經先建好表了 我只需檢查這個數在不在我的表中 04/15 08:24
8F：→ RockLee:就知道它是不是 fair_root 了啊 04/15 08:24
9F：推 ZanFu5566:不知道用0,1,2去建是否對所有N>0都成立呢 04/15 10:37
10F：推 RockLee:第一篇推文中的用0,1,2去建的方法對N>1都成立 04/15 12:09
11F：→ RockLee:(N=1的fair_root是1,2,3) 04/15 12:09
12F：→ RockLee:以題目要求而言3^25~=8*10^11 04/15 12:10
13F：→ RockLee:而我所提的方法實際檢查的candidates低於10^5 04/15 12:10
14F：→ RockLee:故執行速度會更快 不過就這題而言並不一定需要這麼快就是 04/15 12:11