Get a Clue
All submissions for this problem are available.
A group of 5 logicians are playing a game of Clue (also known as Cluedo). The game is played with 18 cards:
6 "suspect" cards, 6 "weapon" cards, and 6 "room" cards (the original game has 9 room cards, but the logicians
have removed 3 in order for everyone to receive the same number of cards). At the beginning of the game, 1 of each type of
card is chosen at random and placed in an envelope, whose contents are kept secret. The remaining cards are
then dealt out randomly to the players, 3 cards each. The goal of the game is
to be the first player to determine which cards are in the envelope. To make things more interesting, the
logicians have modified the rules to the game as follows:
First of all, the cards are each given a unique number: The "suspect" cards are given numbers 1-6, the
"weapon" cards numbers 7-12, and the "room" cards 13-18. At the start of play, each logician announces
the sum of his cards to the group. Then, starting with the first logician and continuing in a circle, each logician
will either pass, or declare himself the winner by announcing the contents of the secret envelope. After the fifth
logician's turn, it becomes the first logician's turn again. The
logicians are very smart, and will never pass if it's possible for them to deduce the contents of the
envelope, nor will they ever attempt to guess the contents of the envelope when they don't know with certainty.
Furthermore, all of the logicians are aware of the fact that none of them will pass if it's
possible to win.
Your task is to determine, given the distribution of the cards, which logician will win (if any).
Input begins with an integer T (about 100), the number of test cases.
Each test case consists of 5 lines of 3 integers each, indicating the cards held by each of the
5 logicians. Each integer will be between 1 and 18, inclusive, and exactly one integer from each
of the ranges 1-6, 7-12, and 13-18 will be absent from each test case. The first line corresponds
to the logician whose turn is first, the second line to the logician whose turn is second,
and so on. Each test case is separated by a blank line
For each test case output a single integer, on a line by itself, indicating the (1-based) index of the
logician who wins the game, or -1 if the game has no winner (i.e. continues forever).
2 6 10 16 3 2 11 8 9 12 15 17 18 4 5 14 1 4 5 7 10 11 3 6 9 12 14 15 16 17 18
In the first example, the cards in the envelope are 1, 7, and 13. All of the logicians immediately know this,
however the first logician wins because it must be one's turn in order to win.
In the second example, the cards in the envelope are 2, 8, and 13. Note that initially the second player does not
have enough information to determine which cards are in the envelope. However, the fact
that the first player passes is enough for the second player deduce the first player's cards (if the first player
had been holding 2 3 5, for example, he would have won instead of pass), which in turn allows him to
determine the secret cards and win.
|Tags||hard, oct10, pieguy|
|Time Limit:||0.216667 sec|
|Source Limit:||50000 Bytes|
|Languages:||ADA, ASM, BASH, BF, C, C99 strict, CAML, CLOJ, CLPS, COB, CPP 4.3.2, CPP 6.3, CPP14, CS2, D, ERL, FORT, FS, GO, HASK, ICK, ICON, JAVA, JS, kotlin, LISP clisp, LISP sbcl, LUA, NEM, NICE, NODEJS, PAS fpc, PAS gpc, PERL, PERL6, PHP, PIKE, PRLG, PYPY, PYTH, PYTH 3.5, RUBY, rust, SCALA, SCM chicken, SCM guile, SCM qobi, ST, swift, TEXT, WSPC|
Fetching successful submissions
If you are still having problems, see a sample solution here.