题目描述
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.
PROGRAM NAME: lamps
Solution
显然的,这四个按钮中,前三个按钮对状态的修改最多每2盏灯改变一盏,而第四个按钮每3盏灯改变一盏,因此灯的状态每隔6盏就会发生重复。可以发现一共有8种不同的选择
- 不按
- 按一个按钮
- 按前三个按钮中的一个以及第四个按钮
容易发现,同一个按钮按两次相当于没按,前三个按钮按任意两个相当于按第三个,如果全按也相当于没按。
我们用一个二维数组存储这8种方案,对于所有方案都适用的情况,把8种方案都判断一遍即可,然后特判只能选前两种方案的情况(即\(C \leq 2\))
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;
n = read<int>();
c = read<int>();
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;
}