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

Just Another 通过思路

Posted by purenanya at 2011-05-04 23:34:33 on Problem 1013
首先,假币检出只有一种条件,就是在一次不平衡的测量中,其余N-1枚均为已知真币。

以下三种情况可以判断一枚钱币为真:
1.出现在一次平衡测量中;
2.既在Up的一端出现过,也在Down的一端出现过;
3.遇到一次不平衡测量时,所有未出现在该测量中的币为真币。

一旦某币被判断为真,保持其状态不再更改。

---------------------------------------------------
本题的一个简化之处是假币必然至少出现在一次测量之中(故不用考虑测量中没有出现的钱币),否则无法断其轻重。

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