A set of \(N\) \((10 \le N \le 100)\) lamps, numbered from 1 to N.
Four types of button:
| Button type | Usage |
|---|
| 1 | flip all lamps (On to Off, Off to On) |
| 2 | flip odd numbered lamps (e.g. 1, 3, 5) |
| 3 | flip even numbered lamps (e.g. 2, 4, 6) |
| 4 | flip \(3k+1 ; with ; k \ge 0\) numbered lamps (e.g. 1, 4, 7) |
Given \(C\) (number of button presses, \(0 \le C \le 10000\)) and final state of some of the lamps, find all possible distinct configuration.
At the start, all lamps are ON and \(C = 0\).
Solution
From the description, we can know that:
Every 6 lamps is a loop, because the least common multiple of 1, 2, 3 (button 1 changes every lamps, button 2 changes one of 2 lamps and button 3 changes one of 3 lamps) is 6.
If you press the same button twice, it has the same affect that if you don’t press the button. In logic symbols, \( \sim(\sim p) = p \). A button only can be switched on or off, and there are 4 types of buttons. Therefore, there are \( 2^4 = 16 \) possibilities.
Then
- for \(C = 0\), check current state
- for \(C = 1\), press each button once
- for \( C \ge 2 \), check every 16 possibilities.
It is a good opportunity to practice bitset though. Take care that bitset does not have build-in sort supported in set :(
Code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
| /*
ID: cepheid1
LANG: C++11
TASK: lamps
*/
#include<fstream>
#include<algorithm>
#include<bitset>
#include<vector>
#include<map>
#include<set>
#include<string>
using namespace std;
ifstream fin("lamps.in");
ofstream fout("lamps.out");
/* convert bitset to store in map and set to get ordered */
set<short> st;
map<short, string>mp;
bitset<6> bt; // simulates 6 lamps
bitset<4> light; // simulates 4 buttons
bool on[7], off[7];
int N, C, a;
bool chk_on() {
for (int i = 0; i < 6 ; i++) {
if (on[i] && !(bt[6-i-1])) return false;
}
return true;
}
bool chk_off() {
for (int i = 0; i < 6 ; i++) {
if (off[i] && (bt[6-i-1])) return false;
}
return true;
}
void op(int x) {
switch(x) {
case 1:
bt.flip();
break;
case 2:
for (int i = 1; i < 6; i+=2) bt.flip(i);
break;
case 3:
for (int i = 0; i < 6; i+=2) bt.flip(i);
break;
case 4:
bt.flip(2);
bt.flip(5);
break;
default:
break;
}
}
int main(void) {
fin >> N >> C;
while (fin >> a && a != -1) {
if (a%6 == 0) on[5] = true;
else on[(a%6-1)] = true;
}
while (fin >> a && a != -1) {
if (a%6 == 0) off[5] = true;
else off[(a%6-1)] = true;
}
fin.close();
bt.set();
if (C == 0) {
if (chk_on() && chk_off()) {
if (!st.count(bt.to_ulong())) {
mp[(short)bt.to_ulong()] = bt.to_string();
st.insert((short)bt.to_ulong());
}
}
} else if (C == 1) {
for (int i = 0; i < 4; i++) {
bt.set();
op(i);
if (chk_on() && chk_off()) {
if (!st.count(bt.to_ulong())) {
mp[(short)bt.to_ulong()] = bt.to_string();
st.insert((short)bt.to_ulong());
}
}
}
} else {
for (int i = 0; i < 16; i++) {
bt.set();
light = i;
for (int j = 0; j < 4; j++) {
if (light[j]) op(j+1);
}
if (chk_on() && chk_off()) {
if (!st.count(bt.to_ulong())) {
mp[(short)bt.to_ulong()] = bt.to_string();
st.insert((short)bt.to_ulong());
}
}
}
}
if (st.empty()) {
fout << "IMPOSSIBLE\n";
} else {
int len = 0;
string s;
for (auto i : st) {
len = 0;
s = "";
while (len <= N) {
s += (mp[i]);
len += (mp[i]).size();
}
fout << s.substr(0, N) << endl;
}
}
fout.close();
return 0;
}
|