[問題] 摳醬的第三題

[vocaloid (void *)]

https://code.google.com/codejam

參考答案好像還沒公佈



請問第三題怎麼作比較有效率呢?

large input 1 - 10 ^ 14
            2 - 10 ^ 100

第一個我是跑測資前先建表 http://ideone.com/DDA2Sn

第二個本來想offline建但不知會跑多久... 10^30就花了3分鐘

--
參考各位意見後的版本 http://ideone.com/abFwJ6

--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 180.176.98.183
推 rebaudiana:我印出答案觀察規律發現一定要是由0, 1, 2構成的迴文數
→ rebaudiana:的平方才有可能是所求，所以應該是3^50 (?)
→ rebaudiana:另外枚舉下一個回文數有常數時間的算法。
→ rebaudiana:另外有沒有人能分享第四題Q_____Q，我只會寫small case
推 paae0226:因為本身也要是迴文所以應該可以再切一半 = 3^25
→ paae0226:然後把平方之後明顯不會是迴文的剪掉就夠快了
※ 編輯: vocaloid        來自: 180.176.98.183       (04/14 23:35)
推 tobygameac:我先用java建表之後程式5萬多行傳不上去 但是答案對了
→ tobygameac:source code不對不知道會不會被扣回來XD
推 seanwu:1. 平方不可以有進位(否則不是迴文)
→ seanwu:2. 中間那位會是所有位數的平方和，不可進位所以<10
→ seanwu:3. 這樣每位就只有 0,1,2,3 少少的幾種組合而已