## IOI '10 P1 - Cluedo

View as PDFDr. Black has been murdered. Detective Jill must determine the murderer, the location, and the weapon. There are six possible murderers, numbered to . There are ten possible locations, numbered to . There are six possible weapons, numbered to .

*For illustration only, we show the names of the possible murderers, locations and weapons. The names are not required to solve the task.*

Murderer | Location | Weapon |
---|---|---|

1. Ballroom | ||

2. Kitchen | ||

1. Professor Plum | 3. Conservatory | 1. Lead Pipe |

2. Miss Scarlet | 4. Dining Room | 2. Dagger |

3. Colonel Mustard | 5. Billiard Room | 3. Candlestick |

4. Mrs. White | 6. Library | 4. Revolver |

5. Reverend Green | 7. Lounge | 5. Rope |

6. Mrs. Peacock | 8. Hall | 6. Spanner |

9. Study | ||

10. Cellar |

Jill repeatedly tries to guess the correct combination of murderer, location and weapon. Each guess is called a *theory*. She asks her assistant Jack to confirm or to refute each theory in turn. When Jack confirms a theory, Jill is done. When Jack refutes a theory, he reports to Jill that one of the murderer, location or weapon is wrong.

You are to implement the procedure **Solve** that plays Jill's role. The grader will call **Solve** many times, each time with a new case to be solved. **Solve** must repeatedly call **Theory(M,L,W)**, which is implemented by the grader. and are numbers denoting a particular combination of murderer, location and weapon. **Theory(M,L,W)** returns if the theory is correct. If the theory is wrong, a value of or is returned. indicates that the murderer is wrong; indicates that the location is wrong; indicates that the weapon is wrong. If more than one is wrong, Jack picks one arbitrarily between the wrong ones (not necessarily in a deterministic way). When **Theory(M,L,W)** returns , **Solve** should return.

#### Example

As example, assume that Miss Scarlet committed the murder (Murderer ) in the conservatory (Location ) using a revolver (Weapon ). When procedure **Solve** makes the following calls to function **Theory**, the results in the second column could be returned.

Call |
Returned value |
Explanation |

Theory(1, 1, 1) |
or or | All three are wrong |

Theory(3, 3, 3) |
or | Only the location is correct |

Theory(5, 3, 4) |
Only the murderer is wrong | |

Theory(2, 3, 4) |
All are correct |

##### Subtask 1 [50 points]

Each test run may call **Solve** up to times. Each call might correspond to a different combination of murderer, location and weapon as the answer. Each time **Solve** is called, it must find the correct theory with no more than calls to **Theory(M,L,W)**. *Be sure to initialize any variables used by Solve every time it is called*.

##### Subtask 2 [50 points]

Each test run may call **Solve** up to times. Each time **Solve** is called, it must find the correct theory with no more than calls to **Theory(M,L,W)**. *Be sure to initialize any variables used by Solve every time it is called*.

#### Implementation Details

- Implementation folder:
`/home/ioi2010-contestant/cluedo/`

(prototype: cluedo.zip) - To be implemented by contestant:
`cluedo.c`

or`cluedo.cpp`

or`cluedo.pas`

- Contestant interface:
`cluedo.h`

or`cluedo.pas`

- Grader interface:
`grader.h`

or`graderlib.pas`

- Sample grader:
`grader.c`

or`grader.cpp`

or`grader.pas`

and`graderlib.pas`

- Sample grader input:
`grader.in.1`

.

*Note: Each line of input contains three numbers denoting the murderer, the location and the weapon.* - Expected output for sample grader input: if
**Solve**correctly solves all cases, the output file will contain`OK t`

where is the maximum number of calls to**Theory**used for any case.

## Comments