[問題] 摳醬的第三題

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