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.

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;
}