IOI'95 Task: Wires and Switches

Task: Wires and Switches

Figure 1: Cable with three wires and three switches

In Figure 1, a cable with three wires connects side A to side B. On side A, the three wires are labeled 1, 2, and 3. On side B, wires 1 and 3 are connected to switch 3, and wire 2 is connected to switch 1.

In general, the cable contains m wires (1<=m<=90), labeled 1 through m on side A, and there are m switches on side B, labeled 1 through m. Each wire is connected to exactly one of the switches. Each switch can be connected to zero or more wires.

Measurements

Your program has to determine how the wires are connected to the switches by doing some measurements. Each switch can be made either conducting or non-conducting. Initially all switches are non-conducting. A wire can be tested on side A with probe P: Lamp L will light up if and only if the sensed wire is connected to a conducting switch.

Your program begins by reading one line with the number m from standard input. It then can give three kinds of commands by writing a line to \emph{standard output}. Each command starts with a single uppercase letter: T (Test a wire), C (Change a switch), and D (Done). Command T is followed by a wire label, C by a switch label, and D by a list whose i-th element is the label of the switch to which wire i is connected.

After commands T and C, your program should read one line from \emph{standard input}. Command T returns Y (Yes) when the wire's switch is conducting (the lamp lights up), otherwise it returns N (No). Command C returns Y if the new switch state is conducting, and N otherwise. The effect of command C is to change the state of the switch (if it was conducting then it will be non-conducting afterwards and vice versa); the result is returned just for feedback.

Your program may give commands T and C mixed in any order. Finally, it gives command D and terminates. Your program should give no more than nine hundred (900) commands in total.

Example

Figure 2 presents an example conversation involving 8 commands relating to Figure 1.

____________________________________
| Standard Output | Standard Input |
|_________________|________________|
__________________| 3              |
| C 3             | Y              |
| T 1             | Y              |
| T 2             | N              |
| T 3             | Y              |
| C 3             | N              |
| C 2             | Y              |
| T 2             | N              |
| D 3 1 3         |________________|
|_________________|

Figure 2: Example conversation

IOI 95