IOI '98 - Setúbal, Portugal
To brighten up the gala dinner of the IOI '98 we have a set of N (10 ≤ N ≤ 100) coloured lamps numbered from 1 to N.
The lamps are connected to four buttons:
- Button 1: When this button is pressed, all the lamps change their state: those that are ON are turned OFF and those that are OFF are turned ON.
- Button 2: Changes the state of all the odd numbered lamps.
- Button 3: Changes the state of all the even numbered lamps.
- Button 4: Changes the state of the lamps whose number is of the form 3K+1 (with K ≥ 0), i.e., 1,4,7,…
There is a counter C which records the total number of button presses.
When the party starts, all the lamps are ON and the counter C is set to zero.
You are given the value of counter C (0 ≤ C ≤ 10 000) and information on the final state of some of the lamps.Write a program to determine all the possible final configurations of the N lamps that are consistent with the given information, without repetitions.
The input will have four lines, describing the number N of lamps available, the number C of button presses, and the state of some of the lamps in the final configuration.
- The first line contains the number N.
- The second line contains the final value of counter C.
- The third line lists the lamp numbers you are informed to be ON in the final configuration, separated by one space and terminated by the integer -1.
- The fourth line lists the lamp numbers you are informed to be OFF in the final configuration, separated by one space and terminated by the integer -1.
The output must contain all the possible final configurations (without repetitions) of all the lamps. Each possible configuration must be written on a different line. Each line has N characters, where the first character represents the state of lamp 1 and the last character represents the state of lamp N. A 0 (zero) stands for a lamp that is OFF, and a 1 (one) stands for a lamp that is ON. You may output the lines in any order.
If there are no possible configurations, output a single line with the word "
IMPOSSIBLE" (without quotes).
10 1 -1 7 -1
In this case, there are 10 lamps and only one button has been pressed. Lamp 7 is OFF in the final configuration.
0000000000 0110110110 0101010101
In this case, there are three possible final configurations:
- All lamps are OFF.
- Lamps 1, 4, 7, 10 are OFF, and lamps 2, 3, 5, 6, 8, 9 are ON.
- Lamps 1, 3, 5, 7, 9 are OFF, and lamps 2, 4, 6, 8, 10 are ON.
Point Value: 15 (partial)
Time Limit: 2.00s
Memory Limit: 32M
Added: Dec 21, 2013
C++03, PAS, C, HASK, ASM, RUBY, PYTH2, JAVA, PHP, SCM, CAML, PERL, C#, C++11, PYTH3