IOI '98 P3 - Party Lamps

View as PDF

Submit solution


Points: 12 (partial)
Time limit: 1.0s
Memory limit: 32M

Problem type
IOI '98 - Setúbal, Portugal

To brighten up the gala dinner of the IOI '98 we have a set of N (10 \le N \le 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 \ge 0), i.e., 1, 4, 7, \dots

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 \le C \le 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 Specification

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 Specification

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. Configurations may be listed in arbitrary order.

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.

If there are no possible configurations, output a single line with the word IMPOSSIBLE.

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.

Comments


  • 2
    Chemiokeusz  commented on July 26, 2022, 3:23 p.m.

    I(somewhat a beginner) spent several hours to solve this, worth it.


  • 2
    mikoSingle  commented on July 12, 2022, 6:48 p.m.

    ooo yes this was very satisfying to get