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