IOI '98 - Setúbal, Portugal

Party Lamps

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.

Input Format

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.

Output Format

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).

Sample Input

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.

Sample Output

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.

All Submissions
Best Solutions

Point Value: 15 (partial)
Time Limit: 2.00s
Memory Limit: 32M
Added: Dec 21, 2013

Languages Allowed:
C++03, PAS, C, HASK, ASM, RUBY, PYTH2, JAVA, PHP, SCM, CAML, PERL, C#, C++11, PYTH3

Comments (Search)

In the original statement from IOI 98, Setubal, there are two more important rules:
- The number of lamps you are informed to be ON, in the final configuration, is less than or equal to 2.
- The number of lamps you are informed to be
OFF, in the final configuration, is less than or
equal to 2.

Do these two rules still apply?

Do not assume these constraints for this version of the task.

The order of the sample output is wrong...

Modification to the problem statement: you can output the lines in any order.