Created
November 6, 2018 03:31
-
-
Save zjucloud/eee320c016e670ddfef111c386ad9b26 to your computer and use it in GitHub Desktop.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
1:平均分三组,A B C | |
A vs B | |
A < B or A > B 看2.1, A == B 看2.2 | |
2.1 | |
说明在A,B里面,由于A和B相对等价,我们可以假设A < B(反过来就把AB互换即可):这样只可能是A有一个硬币轻,或者B有一个硬币重 | |
A和B都分成2+1+1,表示为A1,A3,A4和B1,B3,B4 | |
我们从C里面取正常的硬币X,然后A3 + B1 VS A4 + B4 + X,把A1和B3留下 | |
三种情况: | |
<:2.1.3 | |
>:2.1.4 | |
=:2.1.5 | |
2.1.3 | |
A3 + B1 < A4 + B4 + X | |
说明A3, B4有问题,因为之前是A < B,所以要不是A的只可能轻,B的只可能重, B1, A4如果有问题,应该是>而不是< | |
A3和B4都是一个,所以用3.1.2解法即可 | |
2.1.4 | |
A3 + B1 > A4 + B4 + X | |
反转了,说明B1,A4可能有问题,B1是两个,A4是一个 | |
我们把B1拆成B11和B12,然后B11 + A4 VS X + X: | |
<:说明res = A4 | |
>:res=B11 | |
==:res=B12 | |
2.1.5 | |
A3 + B1 == A4 + B4 + X | |
说明剩下的A1和B3有问题,和2.4类似,拆分A1为A11, A12 | |
然后A11 + B3 VS X + X | |
<: res=A11 | |
>: res=B3 | |
==: res=A12 | |
3.1 | |
说明C有问题 | |
C分为2 + 2: M, N | |
M再分M1, M2,然后M1 VS M2 | |
如果M1 != M2 看3.1.2,否则看3.1.3 | |
3.1.2 M1 != M2 说明M1, M2有一个有问题 | |
取一个正常的X vs M1,如果不平衡,res=M1否则res=M2 | |
3.1.3 | |
说明N里面有问题,和2.3一样,取一个正常的X vs N1,如果不平衡,说明res=N1,否则res=N2 |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment