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:
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).
This requires O(M*N) flips and O(M*N) probes --- in the worst case, all wires are connected to switch M.
Useq binary search to find the switch for a given wire — that is,
This needs M flips and log M probes. Overall one will need N*M flips, and N*log M probes.
Switch on first half. Probe all wires. This splits the wires into those that fall into the first half and those that fall into second half.
Searches in two halves do not interact: Suppose initially we switch on the first half of switches. After fully exploring all wires that lie in first half, we do not have to reset these switches when we continue our binary search into the second half because, for wires connected to the second half, the switches of the first half have no effect.
This solution can be analyzed to give a very simple algorithm.
Suppose we have 8 switches. We enumerate the binary numbers from 000 to 111 in order and arrange them in a column.
0 0 0 0 0 1 0 1 0 0 1 1 1 0 0 1 0 1 1 1 0 1 1 1
We set the switches according to the columns above and probe each wire once for each column setting. Suppose a wire is connected to switch 4. Then, the 3 experiments will yield answers "011". Thus, for each wire, the result of the experiments gives the binary encoding of the switch to which it is connected.
©IARCS 2012–2016
Pěstujeme web | visit: Skluzavky