Editorial for IOI '10 P1 - Cluedo
Submitting an official solution before solving the problem yourself is a bannable offence.
This was intended to be a very easy task. The number of features to be determined (murderer, location, weapon), and the number of options for each feature were intentionally fixed, and not parameterized.
Given that there are
Subtask 1 could be solved by trying each possible theory (three nested for
loops).
Because the response to a refuted theory will identify one feature for which a wrong option was guessed, the search can be expedited. All theories having that wrong option for that particular feature are now ruled out.
Subtask 2 can be solved by a single loop, incrementing whichever feature was wrong (a monotonic search). The total number of options equals
Comments