608 - Counterfeit Dollar
Solution Description : Ad hoc problem Given maximum 12 coins, you can just test whether the three weighings are consistent with each coin being heavy or light. Ans character character is must be in given characters. Separate the given character to three part (even,up,down) After separation even part = union of all even part. up part = intersection of all up part. down part = intersection of all down part. Now, up part = remove all character which is match with even part. down part = remove all character which is match with even part. Example: ED FG even //ED and FG in event part CI AB down //CI in up part and AB in down part A D up // A in down part and D in up part even part = ED ∪ FG = EDFG up part = CI ∩ D = empty down part = AB ∩ A = A up part = empty - EDFG = empty down part = A - EDFG = A So ans is A another example ABCD EFGH even // ABCD and EFGH in even part ABCI EFJK up // ABCI is down part and EFJK in up part ABIJ EFGH even // ABIJ and EFGH in even part even part = ABCD ∪ EFGH ∪ ABIJ ∪ EFGH = ABCDEFGHIJ up part = EFJK down part = ABCI up part = EFJK - ABCDEFGHIJ = K down part = ABCI - ABCDEFGHIJ = empty So ans is K |
||||||||||
608 - Counterfeit Dollar