USACO2.2.4Party 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)

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.

题解：每个操作最多执行一次，因为执行两次相当于没有执行。所以如果输入的操作总次数C大于4，那么反复使C减去2，直到C小于或等于4。我们只需对前六个灯进行操作，因为第六个灯之后的灯都是前六个灯的重复，因此在输入的最终状态时的时候可以mod 6。对于1-4的操作，我们可以使用位运算来实现。

按钮1：XOR （111111）2=63

按钮2：XOR （010101）2=42

按钮3：XOR （101010）2=21

按钮4：XOR （011011）2=36

进行DFS时每次搜的时候只有两种状态，要么进行当前操作，要么不执行。所以DFS很容易写出来。

View Code

  1 /*
  2 ID:spcjv51
  3 PROG:lamps
  4 LANG:C
  5 */
  6 #include<stdio.h>
  7 #define MAXSTEP 4
  8 int c,n,ans,total;
  9 int a[10],f[10],b[10];
 10 int compare(const void*a,const void*b)
 11 {
 12     return(*(int*)a-*(int*)b);
 13 }
 14 void chai(int tt)
 15 {
 16     int i;
 17     i=0;
 18     memset(b,0,sizeof(b));
 19     while(tt)
 20     {
 21         i++;
 22         b[i]=tt&1;
 23         tt>>=1;
 24     }
 25 }
 26 void check(int sum,int t)
 27 {
 28     int i,tt;
 29     memset(b,0,sizeof(b));
 30     if(t>c||(c-t)%2!=0) return;
 31     chai(sum);
 32     for(i=1; i<=6; i++)
 33     {
 34         if(a[6-i+1]==-1) continue;
 35         if(a[6-i+1]!=b[i]) break;
 36     }
 37     if(i>6)
 38     {
 39         total++;
 40         f[total]=sum;
 41     }
 42 }
 43 void dfs(int step,int t)
 44 {
 45     if(step>MAXSTEP)
 46     {
 47 
 48          check(ans,t);
 49         return;
 50     }
 51     t++;
 52     if(step==1) ans=ans^63;
 53     if(step==2) ans=ans^42;
 54     if(step==3) ans=ans^21;
 55     if(step==4) ans=ans^36;
 56     dfs(step+1,t);
 57     t--;
 58     if(step==1) ans=ans^63;
 59     if(step==2) ans=ans^42;
 60     if(step==3) ans=ans^21;
 61     if(step==4) ans=ans^36;
 62     dfs(step+1,t);
 63 }
 64 void print()
 65 {
 66     int i,j;
 67     for(i=1;i<=total;i++)
 68     {
 69         chai(f[i]);
 70         int c[10];
 71         for(j=1;j<=6;j++)
 72             c[6-j+1]=b[j];
 73     for(j=1; j<n; j++)
 74             printf("%d",c[(j-1)%6+1]);
 75         printf("%d\n",c[(j-1)%6+1]);
 76     }
 77 }
 78 int main(void)
 79 {
 80     freopen("lamps.in","r",stdin);
 81     freopen("lamps.out","w",stdout);
 82     int i,m,j,temp;
 83     scanf("%d",&n);
 84     scanf("%d",&c);
 85     memset(a,-1,sizeof(a));
 86     while(scanf("%d",&m)!=EOF&&m!=-1)
 87         a[(m-1)%6+1]=1;
 88     while(scanf("%d",&m)!=EOF&&m!=-1)
 89     {
 90 
 91         if(a[(m-1)%6+1]!=-1)
 92         {
 93             printf("IMPOSSIBLE\n");
 94             return 0;
 95         }
 96         a[(m-1)%6+1]=0;
 97     }
 98     while(c>4) c-=2;
 99     ans=63;
100     total=0;
101     dfs(1,0);
102     qsort(f,total,sizeof(int),compare);
103     if(total==0)
104     printf("IMPOSSIBLE\n");
105     else
106         print();
107     return 0;
108 }