Online Judge | Problem Set | Authors | Online Contests | User | ||||||
---|---|---|---|---|---|---|---|---|---|---|
Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest |
Re:不用再怀疑,WA的看这里了In Reply To:不用再怀疑,WA的看这里了 Posted by:ycdoit at 2011-03-16 15:04:54 > 最初想法: > 1.出现在even式中的两边都是真币 > 2.一个硬币在不同称重中,分别属于偏重和偏轻的一端,则它是真币 > 3.如果三次称重后,不是真币的就输出偏重或者偏轻 > > 结果是WA,事实上,只要修改一下第三点就可以了 > > 3.三次称重后,如果不是真币,并且偏重或者偏轻的次数等于称重不是even的次数,就输出偏重或者偏轻 > > 分析:我们容易觉得,如果满足最初那3点,还没有被排除的,就可以断定是假币。事实上,我们忘了另一个必要条件:该假币偏重或者偏轻的次数应该==称重不平衡的次数。原因很简单:在每次称重不平衡的时候,假币都会出现。 > 因此应该加上这个判断,才可以。所以可能有多个假币在前面三步还没有被排除,再加这个条件就可以了。 我的想法和你相似,我的最后一个判断是偏重或偏轻次数最多的币是假币,道理是一样的,但是就是不停的WA Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator