Editorial for COI '14 #2 Kovanice
Submitting an official solution before solving the problem yourself is a bannable offence.
Let's first imagine there aren't any weighings in which both sides are equal. We will construct a graph where each weighing
It is clear that this graph cannot have a chain longer than K1
, the second K2
and so on until the KN
. The coins not located in any chain of length
Now it is also possible to process the weighings in which both sides are equal. All coins of equal weight can be combined in one node and run the previously described algorithm on this graph. It is necessary to remember which coins are in which node so we can output the result for each of them.
Comments