PSWITCH - Party Switching
Seraph is a smart boy who, one day at the time of his birthday he was wearing a lot of lights for the event. The number of lights is installed for as many as N, which are numbered 1 through N. lights are connected to a controller that has 4 buttons. Each button functions as follows:
- if this button is pressed, then all light will change the state from OFF to ON or from ON to OFF.
- if this button is pressed, then the odd-numbered light will change its state.
- if this button is pressed, then the even-numbered light will change its state.
- if this button is pressed, all lights are numbered 3K +1 will change its state.
In the controller, there are counter C that count number of button will be pressed. when the initial state, the state of all the lights are ON and the counter C is set to 0. After that you will be given information of light at the end of the show, and you have to count how many kinds of configuration according to the information provided.
Input
The first line containing N (10 <= N <= 100) that indicates number of lamps. The second line is C (1 <= C <= 1000) that indicate the final value of the counter. The third line is lists the number of ON lights at the end of the show, each number separated by a space and the end of the line given the value -1. The fourth line is lists the number of OFF light at the end of the show, each number separated by a space and the end of the line given the value -1.
Output
The possible configurations at the end of the event. There should be no repetitive configuration and output must be in lexicographical. If there is no configuration, print "Impossible".
Example
Input: 10 1 -1 7 -1 Output: 0000000000 0101010101 0110110110
Explanation
There is 10 lamps in that event and you have to press the button once, and at the end of event, lamp number 7 must be OFF.
0 mean that lamp is OFF, 1 mean that lamp is ON.
hide comments
nadstratosfer:
2021-06-04 00:57:44
What does translation of the statement to retarded adds here? Original:
|
|
!(NULL):
2011-11-20 13:48:22
easy problem :) |
|
Johannes Laire:
2012-02-28 14:43:39
@irakli: You are correct, this problem is also at USACO's training site and originally it is from IOI 1998 (called "Party Lamps").
|
Added by: | [Retired] Fendy Kosnatha |
Date: | 2011-03-10 |
Time limit: | 0.100s-0.5s |
Source limit: | 50000B |
Memory limit: | 1536MB |
Cluster: | Cube (Intel G860) |
Languages: | All except: ASM64 |
Resource: | IOI 1998 |