Re: [問題] 摳醬的第三題
看板Prob_Solve作者RockLee (Now of all times)時間11年前 (2013/04/14 19:51)推噓2(2推 0噓 0→)留言2則, 2人參與討論串2/4 (看更多)
※ 引述《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 的表也夠快
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 1.161.10.8
推
04/14 23:27, , 1F
04/14 23:27, 1F
推
04/15 00:31, , 2F
04/15 00:31, 2F
討論串 (同標題文章)