Figura 1: Un circuito con tre fili e tre interruttori
Figura 1: Un circuito con tre fili e tre interruttori
Nella Figura 1, compare un circuito in cui tre fili (sul lato A) sono collegati ad altrettanti interruttori (sul lato B). In questo caso, i tre fili con etichette 1, 2, 3 sono collegati come segue: i fili 1 e 3 sono collegati all'interruttore 3, mentre il filo 2 è collegato all'interruttore 1.
In generale, il circuito contiene m fili (1 <= m <=90), etichettati da 1 a m, sul lato A, e m interruttori, anch'essi etichettati da 1 a m, sul lato B. Ogni filo è collegato ad esattamente uno degli interruttori, ma un interruttore può essere collegato a zero o più fili.
Lo scopo del programma è determinare a quale interruttore è collegato ciascun filo mediante una sequenza di misurazioni. Ogni interruttore può essere chiuso (cioè, condurre corrente) o aperto; inizialmente tutti gli interruttori sono aperti.
Si può testare un filo dal lato A, mediante lo spinotto P: la lampadina L si accenderà se e solo se lo spinotto viene posto su un filo che è collegato ad un interruttore chiuso.
All'inizio, il vostro programma legge una singola riga contenente il numero m, dallo standard input. A questo punto, il programma può dare tre tipi di comandi, scrivendo una riga sullo standard output. Ogni comando inizia con una singola lettera maiuscola: T (Testa un filo), C (Cambia lo stato di un interruttore), o D (Done = Finito).
Il comando T è seguito dall'etichetta di un filo; il comando C è seguito dall'etichetta di un interruttore; il comando D da una lista di m interi, in cui l'i-esimo elemento è l'etichetta dell'interruttore a cui è collegato il filo i.
Dopo i comandi T e C, il vostro programma deve leggere una riga dallo standard input, contenente l'esito del comando. Il comando T restituisce Y (Yes = Sì) se l'interruttore a cui il filo testato è collegato è chiuso (cioè, se la lampadina si accende), altrimenti restituisce N (No).
Il comando C restituisce Y se il nuovo stato dell'interruttore è chiuso, e N in caso contrario. L'effetto del comando C è di cambiare lo stato di un interruttore (se era chiuso, il comando C lo apre, e viceversa): il risultato del comando viene restituito solo come feedback.
Il vostro programma può dare comandi T e C in qualunque ordine. Alla fine, deve dare il comando D e terminare. Il vostro programma non deve dare più di novecento (900) comandi in tutto.
La Figura 2 mostra un esempio di conversazione fra il vostro programma e l'ambiente; le risposte sono relative all'esempio di Figura 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 |________________| |_________________|Figura 2: Esempio di conversazione