作者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