Skip to content

Instantly share code, notes, and snippets.

@zjucloud
Created November 6, 2018 03:31
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save zjucloud/eee320c016e670ddfef111c386ad9b26 to your computer and use it in GitHub Desktop.
Save zjucloud/eee320c016e670ddfef111c386ad9b26 to your computer and use it in GitHub Desktop.
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