作者Leon (Achilles)
站内Prob_Solve
标题Re: [问题] 抠酱的第三题
时间Mon Apr 15 07:13:19 2013
※ 引述《RockLee (Now of all times)》之铭言：
: ※ 引述《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 的表也够快
嗯.. 你确定吗?
用 0,1,2 去造的好处是可以处理 进位 的状况
但, 考虑一下这个数字
522808225
这个是用 5 当个位数造出来的.
请问你的规律性找的到这个数字吗?
实际上, 就我所知, 这仍然是个 open problem.
这里有解释 necessay condition, 但是没有给出 sufficient.
http://arxiv.org/pdf/1210.7593v1.pdf
这个作者颇有名气, 不过这篇还没有 review 过
所以读的时候自己要注意.
--
※ 发信站: 批踢踢实业坊(ptt.cc)
◆ From: 142.136.125.30
1F：推 RockLee:522808225 本身是回文 但它的平方不是回文 04/15 07:40
2F：→ RockLee:不符合我所称的 fair_root 的定义 04/15 07:41
3F：→ Leon:my question is simple, based on you rule 04/15 07:53
4F：→ Leon:how can I decide if the number I point out is or not? 04/15 07:53
5F：推 RockLee:根据我的rule 522808225显然不是 因为它不在我建的表中 04/15 08:05
6F：→ Leon:then, how do you handle this case? 04/15 08:10
7F：推 RockLee:既然我已经先建好表了 我只需检查这个数在不在我的表中 04/15 08:24
8F：→ RockLee:就知道它是不是 fair_root 了啊 04/15 08:24
9F：推 ZanFu5566:不知道用0,1,2去建是否对所有N>0都成立呢 04/15 10:37
10F：推 RockLee:第一篇推文中的用0,1,2去建的方法对N>1都成立 04/15 12:09
11F：→ RockLee:(N=1的fair_root是1,2,3) 04/15 12:09
12F：→ RockLee:以题目要求而言3^25~=8*10^11 04/15 12:10
13F：→ RockLee:而我所提的方法实际检查的candidates低於10^5 04/15 12:10
14F：→ RockLee:故执行速度会更快 不过就这题而言并不一定需要这麽快就是 04/15 12:11