Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

Re: 不必怀疑

Posted by aoxboxcox at 2008-08-23 11:05:56 on Problem 1013
In Reply To:一个通过的思路 Posted by:wrong123 at 2005-12-05 17:31:39
这种解法是正确的。
即使面临这样的问题也能得到答案。
A  B  EVEN
BCDE FGHI  UP
CDEF BGHI  DOWN
虽然CDE和GHI被怀疑两次,但两次都以反方向计。
B和F也被怀疑两次,且以同方向计,权值B、F最大。
但B已经是真币了。这样可以得到F是假币。
用反正法很容易证得,如果该方法判断不出,则题设本身是多解的。
因为要想有两个以上权值一样的最大值出现,那么它(们)必然始终同假币一同出现,或在一起或在对面,相对位置固定不变。
如果那些真币不参与even条件以证真身的话(even不会改变权重),那么只能是多解的。
HHB算法的正确性是显而易见的,但这个方法也是正确的。

Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator