Here's my algorithm. If you don't understand it, well, spend some time figuring it out.
Pile#: 1 2 3 4 5 6 7 8 9 0 1 2 3
Selected: 4 4 4 3 3 3 2 2 2 1 1 1 0 => 30 coins
// This is the first weighing
expected weight = 30X
actual weight = W
X1 = W div 30
D1 = W mod 30 // D1 <= 20 since |D| <= 5 and counterfeit coins in pile <= 4
if D1 == 0 then
weigh all 52 coins (W) // this is the second weighing
X = W div 52
D = (W mod 52) / 4
pile = 13
else if D1 <= 5 then
possible piles = 1-12
else if D1 >= 25 then
X1 = X1 + 1,
D1 = 30 - D1
possible piles = 1-12
else if 5 < D1 < 10 then
possible piles = 1-9
else if 10 <= D1 <= 20
X11 = X1 + 1,
D11 = 30 - D1
possible piles = 1-6
end if
if 0 < D1 < 10 then
Pile#: 1 2 3 4 5 6 7 8 9 0 1 2 3
Selected: 1 3 4 1 2 4 0 1 3 2 3 4 4 => 32 coins
// This is the second weighing
expected weight = 32X
actual weight = W
X2 = W div 32
D2 = W mod 32 // D2 <= 20 since |D| <= 5 and counterfeit coins in pile <= 4
if 12 <= D2 <= 20 and X1 != X2 then
X2 = X2 + 1
D2 = 32 - D2
end if
X = X2
if D2 == D1*0 then
pile = 7
D = D1/2
else if D2 == D1*1 then
pile = 3
D = D1/4
else if D2 == D1*2 then
pile = 10
D = D1
else if D2 == D1*3 then
pile = 11
D = D1
else if D2 == D1*4 then
pile = 12
D = D1
else if D2 == D1*1/2 then
pile = 8
D = D1/2
else if D2 == D1*3/2 then
pile = 9
D = D1/2
else if D2 == D1*1/3 then
pile = 4
D = D1/3
else if D2 == D1*2/3 then
pile = 5
D = D1/3
else if D2 == D1*4/3 then
pile = 6
D = D1/3
else if D2 == D1*1/4 then
pile = 1
D = D1/4
else if D2 == D1*3/4 then
pile = 2
D = D1/4
end if
else
Pile#: 1 2 3 4 5 6 7 8 9 0 1 2 3
Selected: 1 2 3 0 1 2 4 4 4 4 4 4 4 => 37 coins
// This is the second weighing
expected weight = 37X
actual weight = W
X2 = W div 37
D2 = W mod 37 // D2 <= 15 since |D| <= 5 and counterfeit coins in pile <= 3
X = X2
if X11 == X2 then
D1 = D11
end if
if D2 == D1*1/4 then
pile = 1
D = D1/4
else if D2 == D1*2/4 then
pile = 2
D = D1/4
else if D2 == D1*3/4 then
pile = 3
D = D1/4
else if D2 == D1*0/3 then
pile = 4
D = D1/3
else if D2 == D1*1/3 then
pile = 5
D = D1/3
else if D2 == D1*2/3 then
pile = 6
D = D1/3
end if
end if
0 comments :
Post a Comment