A television game show host begins each new game by selecting a player, as follows. The host asks candidate players to order four items. The first candidate to order the items correctly wins. If there is a tie for the fastest time, or if no one correctly answers, the host poses a new question. The producers air only questions that select a player. They are unhappy with their current player selection software and are seeking a replacement.
The candidates have at most 30 seconds to answer the question. During this time, they press buttons A, B, C, or D, indicating how to order the items. Pressing a special rub out button marked X erases the last selection (this has no effect if there are no characters to rub out). For example, after pressing BXXACXDXBDC, the candidate has selected the answer ABDC. Each candidate's selection is sent to the software along with a timestamp (from 0 to 300, in tenths of a second) and a number identifying the candidate. A candidate cannot make simultaneous selections (i.e., with the same timestamp), but two different candidates might make selections at the same time. Although the software receives the messages in time sequence for a particular candidate, messages from two different candidates may arrive out of time sequence. For example, the software might receive the following sequence:
Candidate |
Timestamp |
Selection |
Interpretation |
1 |
20 |
B |
Candidate 1 selected B at time 20 (answer: B) |
2 |
10 |
B |
Candidate 2 selected B at time 10 (answer: B) |
1 |
50 |
C |
Candidate 1 selected C at time 50 (answer: BC) |
2 |
40 |
D |
Candidate 2 selected D at time 40 (answer: BD) |
1 |
70 |
X |
Candidate 1 erased C at time 70 (answer: B) |
1 |
110 |
D |
Candidate 1 selected D at time 110 (answer: BD) |
1 |
120 |
A |
Candidate 1 selected A at time 120 (answer: BDA) |
2 |
100 |
A |
Candidate 2 selected A at time 100 (answer: BDA) |
2 |
150 |
C |
Candidate 2 selected C at time 150 (answer: BDAC) |
1 |
170 |
C |
Candidate 1 selected C at time 170 (answer: BDAC) |
Suppose that the correct item order is BDAC. To be considered correct, a candidate's final answer must exactly match the correct item order. In this example, both candidates have the correct answer, but Candidate 2 has the faster time (15.0 seconds), and is the player for the next round.