Algorithm 版 (精华区)

发信人: Lerry (想不开·撞树), 信区: Algorithm
标  题: Task: Wires and Switches
发信站: 哈工大紫丁香 (2002年03月29日13:52:18 星期五), 站内信件

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 connec
ted 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 si
de 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 ze
ro 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-c
onducting. Initially all switches are non-conducting. A wire can be tested o
n side A with probe P: Lamp L will light up if and only if the sensed wire i
s connected to a conducting switch.
Your program begins by reading one line with the number m from standard inpu
t. It then can give three kinds of commands by writing a line to \emph{stand
ard output}. Each command starts with a single uppercase letter: T (Test a w
ire), C (Change a switch), and D (Done). Command T is followed by a wire lab
el, 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{standar
d input}. Command T returns Y (Yes) when the wire's switch is conducting (th
e lamp lights up), otherwise it returns N (No). Command C returns Y if the n
ew switch state is conducting, and N otherwise. The effect of command C is t
o change the state of the switch (if it was conducting then it will be non-c
onducting afterwards and vice versa); the result is returned just for feedba
ck.
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 hundre
d (900) commands in total.
Example
Figure 2 presents an example conversation involving 8 commands relating to F
igure 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

--
不在乎天长地久，就怕你从来没有！

※ 来源:·哈工大紫丁香 bbs.hit.edu.cn·[FROM: 天外飞仙]