# USACO 2.2 Party Lamps

### 题目描述

To brighten up the gala dinner of the IOI'98 we have a set of N (10 <= N <= 100) colored 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 3xK+1 (with K>=0), i.e., 1,4,7,...

A counter C 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 <= 10000) and the final state of some of the lamps after some operations have been executed. Write a program to determine all the possible final configurations of the N lamps that are consistent with the given information, without repetitions.

### Solution

• 不按
• 按一个按钮
• 按前三个按钮中的一个以及第四个按钮

### Code

/*
PROB: lamps
LANG: C++
ID: yizhuor1
*/
#include <bits/stdc++.h>
#define pb push_back
#define mp make_pair

using namespace std;

typedef long long LL;
typedef pair<int, int> pii;

template <typename T> inline int Chkmax (T &a, T b) { return a < b ? a = b, 1 : 0; }
template <typename T> inline int Chkmin (T &a, T b) { return a > b ? a = b, 1 : 0; }

template <typename T> inline T read(){
T sum = 0;
int fl = 1,ch = getchar();
for(; !isdigit(ch); ch = getchar()) if(ch == '-') fl = -1;
for(; isdigit(ch); ch = getchar()) sum = (sum << 3) + (sum << 1) + ch - '0';
return sum * fl;
}

const int maxn = 10 + 5;

int n,c,flag;
int book[maxn];
int a[maxn][maxn] = {
{0,0,0,0,0,0,0},
{0,0,0,1,1,1,0},
{0,0,1,0,1,0,1},
{0,0,1,1,0,1,1},
{0,1,0,0,1,0,0},
{0,1,0,1,0,1,0},
{0,1,1,0,0,0,1},
{0,1,1,1,1,1,1}
};

void check(int x){
for(int i = 1; i <= 6; i++) if(book[i] != -1 && a[x][i] != book[i]) return;
for(int i = 1; i <= n; i++) printf("%d",a[x][(i - 1) % 6 + 1]);
printf("\n");
flag = 1;
}

inline void Solve (){
if(!c){
check(7);
if(flag) return;
}else if(c == 1){
check(0);
check(2);
check(3);
check(5);
if(flag) return;
}else if(c == 2){
check(0);
check(1);
check(2);
check(4);
check(5);
check(6);
check(7);
if(flag) return;
}else{
for(int i = 0; i <= 7; i++) check(i);
if(flag) return;
}
if(!flag) printf("IMPOSSIBLE\n");
}

inline void Input (){
int x;
for(int i = 0; i < maxn; i++) book[i] = -1;
while(~scanf("%d",&x)){
if(x == -1) break;
book[(x - 1) % 6 + 1] = 1;
}
while(~scanf("%d",&x)){
if(x == -1) break;
book[(x - 1) % 6 + 1] = 0;
}
}

int main(){
Input();
Solve();
return 0;
}