Party Lamps（分析 + 模拟）

Party Lamps
IOI 98

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

INPUT FORMAT

No lamp will be listed twice in the input.

Line 1:	N
Line 2:	Final value of C
Line 3:	Some lamp numbers ON in the final configuration, separated by one space and terminated by the integer -1.
Line 4:	Some lamp numbers OFF in the final configuration, separated by one space and terminated by the integer -1.

SAMPLE INPUT (file lamps.in)

10
1
-1
7 -1

In this case, there are 10 lamps and only one button has been pressed. Lamp 7 is OFF in the final configuration.

OUTPUT FORMAT

Lines with all the possible final configurations (without repetitions) of all the lamps. Each line has N characters, where the first character represents the state of lamp 1 and the last character represents the state of lamp N. A 0 (zero) stands for a lamp that is OFF, and a 1 (one) stands for a lamp that is ON. The lines must be ordered from least to largest (as binary numbers).

If there are no possible configurations, output a single line with the single word `IMPOSSIBLE'

SAMPLE OUTPUT (file lamps.out)

0000000000
0101010101
0110110110

In this case, there are three possible final configurations:

• All lamps are OFF
• Lamps 1, 4, 7, 10 are OFF and lamps 2, 3, 5, 6, 8, 9 are ON.
• Lamps 1, 3, 5, 7, 9 are OFF and lamps 2, 4, 6, 8, 10 are ON.

    题意：

    给出 N（10 ~ 100）盏灯 ，C （0 ~ 10000）个按钮，后给出要求，要求亮灯的序号（-1结束）再给出暗灯的序号（-1结束），输出在 C 次按钮下最终可能的灯两暗情况。

    按钮1：改变全部灯当前的状态；

    按钮2：改变奇数灯当前的状态；

    按钮3：改变偶数灯当前的状态；

    按钮4：改变 3 * k + 1 灯当前的状态 （1,4,7,10,13……）。

 

    思路：

    1.改变偶数次灯等于回到原来的状态，改变奇数次等于改变一次即与当前状态相反；

    2.选择按钮的次序不影响最终结果，即 2,1,3 与 1,2,3 是一样的；

    明确两点后可以分析：

    若 C == 1，有四种选择，1,2,3,4；

    若 C == 2，故有 C（4，2）共 6 种选择；

    若 C == 3，如果只是选1种，比如选1，那么就是1,1,1，同 C == 1的情况相同，故只选一种的话有4种可能；

                       如果只是选2种，比如选1,2，那么就是1,2,2，同C == 1 的情况相同，故这种情况排除；

                       如果只是选3种，比如选1,2,3，那么就是 C（4，3）共 4 种情况；

    若 C == 4，如果只是选1种，比如选1，那么就是 1,1,1,1，相当于没变，故这种情况可以排除；

                      如果只是选2种，比如选 1,2，那么就是1,2,1,2相当于没变，排除，或者1,2,2,2 相当于1,2，故与 C == 2 的情况相同 6 种；

                      如果只是选3种，比如选 1,2,3，那么就是1,2,3,3 相当于选两种，排除；

                      选4种，即 1,2,3,4 全选 1 种；

    如此列举，可以得出：

    C == 1 时，选其中 1 个；

    C == 2 时，选其中 2 个；

    C > 2 为奇数时，选其中 1 个或者 3 个；

    C > 2 为偶数时，选其中 2 个或者 4 个；

    把可能的情况列出来后还要二进制排序，因为最多可能有100位，故只需要列举前 6 位排序即可。

 

    AC：

/*    
TASK:lamps    
LANG:C++    
ID:sum-g1    
*/
#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
typedef struct
{
    int bin[105];
    int num;
}node;

node no[1000];
int lamp[105],on[105],off[105];
int n,c,on_sum,off_sum,sum;

int cmp(node a,node b)
{
    return a.num < b.num;
}

void init()
{
    for(int i = 1;i <= n;i++) lamp[i] = 1;
}

void bin_in()
{
    int k = 1,ans = 0;
    for(int i = 6;i >= 1;i--)
    {
        ans += lamp[i] * k;
        k *= 2;
    }
    sum++;
    no[sum].num = ans;
    for(int i = 1;i <= n;i++)
        no[sum].bin[i] = lamp[i];
}

void test()
{
    for(int i = 0;i < on_sum;i++)
        if(!lamp[on[i]]) return;
    for(int i = 0;i < off_sum;i++)
        if(lamp[off[i]]) return;
    bin_in();
}

void bin_out()
{
    for(int j = 1;j <= sum;j++)
    {
        for(int i = 1;i <= n;i++)
            printf("%d",no[j].bin[i]);
        printf("\n");
    }
}

void way1()
{
    for(int i = 1;i <= n;i++)
    {
        if(lamp[i]) lamp[i] = 0;
        else        lamp[i] = 1;
    }
}

void way2()
{
    for(int i = 1;i <= n;i += 2)
    {
        if(lamp[i]) lamp[i] = 0;
        else        lamp[i] = 1;
    }
}

void way3()
{
    for(int i = 2;i <= n;i += 2)
    {
        if(lamp[i]) lamp[i] = 0;
        else        lamp[i] = 1;
    }
}

void way4()
{
    for(int i = 1;i <= n;i += 3)
    {
        if(lamp[i]) lamp[i] = 0;
        else        lamp[i] = 1;
    }
}

void choose1()
{
    init();way1();test();
    init();way2();test();
    init();way3();test();
    init();way4();test();
}

void choose2()
{
    init();way1();way2();test();
    init();way1();way3();test();
    init();way1();way4();test();
    init();way2();way3();test();
    init();way2();way4();test();
    init();way3();way4();test();
}

void choose3()
{
    init();way1();way2();way3();test();
    init();way1();way2();way4();test();
    init();way1();way3();way4();test();
    init();way2();way3();way4();test();
}

void choose4()
{
    init();way1();way2();
    way3();way4();test();
}

int main()
{
    freopen("lamps.in","r",stdin);        
    freopen("lamps.out","w",stdout);
    int num;
    on_sum = 0,off_sum = 0,sum = 0;
    scanf("%d%d",&n,&c);
    for(int i = 1;i <= n;i++)   lamp[i] = 1;
    while(~scanf("%d",&on[on_sum]))
    {
        if(on[on_sum] == -1) break;
        on_sum++;
    }
    while(~scanf("%d",&off[off_sum]))
    {
        if(off[off_sum] == -1) break;
        off_sum++;
    }
    test();
    if(c == 1)  choose1();
    if(c == 2)  choose2();
    if(c > 2)
    {
        if(c % 2)
        {
            choose1();choose3();
        }
        else
        {
            choose2();choose4();
        }
    }
    if(!sum)    printf("IMPOSSIBLE\n");
    else
    {
        sort(no + 1,no + sum + 1,cmp);
        bin_out();
    }
    return 0;
}