Indian Computing Olympiad

Searching→Wires and Switches (IOI 1995)

You have N wires and M switches. Each wire is connected to some switch, but two wire may be connected to the same switch.

                 Points  Switches
                   .       ./ .--
                   .\      ./ .--|
        --Probe->  ._\__   ./ .--|---
       |           .  \ \__./ .--|   |
       |           .___\_/ ./ .--|   |
       |           .    \__./ .--    |
       |                             |
        -----------------------------
      

All switches are simultaneously connected to a probe. We can connect a probe to a wire to check if circuit is complete with current values of switches.

Two commands are available to you:

• Flip(j) — Flip switch j
• Probe(i) — Check if the circuit to wire i is complete

The goal is to determine, for each wire, the switch to which that wire is connected, using no more than 900 of Change and Probe commands. The number of wires and switches is in the range 1..90. Initially, all switches are off (open).

Solution

---