# USACO Party Lamps

Contents

A set of $$N$$ $$(10 \le N \le 100)$$ lamps, numbered from 1 to N.

Four types of button:

Button typeUsage
1flip all lamps (On to Off, Off to On)
2flip odd numbered lamps (e.g. 1, 3, 5)
3flip even numbered lamps (e.g. 2, 4, 6)
4flip $$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:

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

2. 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 #include #include #include #include #include #include using namespace std; ifstream fin("lamps.in"); ofstream fout("lamps.out"); /* convert bitset to store in map and set to get ordered */ set st; mapmp; 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; }