作者vocaloid (void *)
看板Prob_Solve
標題[問題] 摳醬的第三題
時間Sun Apr 14 18:29:35 2013
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
1F：推 rebaudiana:我印出答案觀察規律發現一定要是由0, 1, 2構成的迴文數 04/14 19:46
2F：→ rebaudiana:的平方才有可能是所求，所以應該是3^50 (?) 04/14 19:47
3F：→ rebaudiana:另外枚舉下一個回文數有常數時間的算法。 04/14 19:48
4F：→ rebaudiana:另外有沒有人能分享第四題Q_____Q，我只會寫small case 04/14 19:49
5F：推 paae0226:因為本身也要是迴文所以應該可以再切一半 = 3^25 04/14 20:01
6F：→ paae0226:然後把平方之後明顯不會是迴文的剪掉就夠快了 04/14 20:02
※ 編輯: vocaloid 來自: 180.176.98.183 (04/14 23:35)
7F：推 tobygameac:我先用java建表之後程式5萬多行傳不上去 但是答案對了 04/15 12:18
8F：→ tobygameac:source code不對不知道會不會被扣回來XD 04/15 12:18
9F：推 seanwu:1. 平方不可以有進位(否則不是迴文) 04/15 18:50
10F：→ seanwu:2. 中間那位會是所有位數的平方和，不可進位所以<10 04/15 18:52
11F：→ seanwu:3. 這樣每位就只有 0,1,2,3 少少的幾種組合而已 04/15 18:52