[usaco][舞会灯] 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
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.
No lamp will be listed twice in the input.

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.
---------------------------------------------------------------------------

1：对于每一个button，如果按下两次，就相当于什么也没发生。
2：对于所有的等，相当于6盏灯。

-----------------------------------------------------------------------------

/*
ID:yunleis2
PROG:lamps
LANG:C++
*/
#include<iostream>
#include<fstream>
#include<vector>
using namespace std;
int N;
int C;
int *final_on;
int *final_off;
void search(int depth,bool * state0);
vector<bool *> result;
void quicksort(bool ** a,int p,int r);
int compare(bool * b1,bool *b2);
void button1(int num,bool *state0);
void button2(int num,bool *state0);
void button3(int num,bool *state0);
void button4(int num,bool *state0);
void check(int num,bool *state0);
int main()
{
fstream fin("lamps.in",ios::in);
fin>>N;
int old_n=N;
N--;
N=N%6+6;
N++;
fin>>C;
int t;
final_on=new int[N+1];
final_off=new int[N+1];
bool * init_s=new bool[N];
for(int i=0;i<N;i++)
init_s[i]=true;
int ptr=0;
do{
fin>>t;
final_on[ptr++]=t-1;
}while(t!=-1);
ptr=0;
do{
fin>>t;
final_off[ptr++]=t-1;
}while(t!=-1);
//search(C,init_s);
button1(0,init_s);

bool **result1 =new bool*[result.size()];
int size=result.size();
for(int i=0;i<result.size();i++)
{
result1[i]=result.at(i);
}
for(int i=0;i<size;i++)
{
for(int j=0;j<N;j++)
cout<<result[i][j];
cout<<endl;

}
quicksort(result1,0,result.size()-1);
fstream fout("lamps.out",ios::out);
if(size==0)
fout<<"IMPOSSIBLE"<<endl;
cout<<endl;
for(int i=0;i<size;i++)
{
if(i!=0&&compare(result1[i],result1[i-1])==0)
{
continue;
}
for(int j=0;j<old_n;j++)
fout<<result1[i][j%6];
fout<<endl;

}
for(int i=0;i<size;i++)
delete [] result1[i];

}
int compare(bool * b1,bool *b2)
{
#if 0

cout<<"compare"<<endl;
for(int j=0;j<N;j++)
cout<<b1[j];
cout<<endl;
for(int j=0;j<N;j++)
cout<<b2[j];
cout<<endl;
#endif

for(int i=0;i<N;i++)
{
int a=b1[i];
int b=b2[i];
if(a<b)
return -1;
if(a>b)
return 1;
}
return 0;
}
int partition(bool ** a,int p,int r)
{
bool * x=a[r];
int i=p-1;
for(int j=p;j<r;j++)
{
if(compare(a[j],x)<=0)
{
i++;
bool * temp=a[i];
a[i]=a[j];
a[j]=temp;
}
}
bool * temp=a[i+1];
a[i+1]=a[r];
a[r]=temp;
return i+1;
}
void quicksort(bool ** a,int p,int r)
{
if(p<r)
{
int i=partition(a,p,r);
quicksort(a,p,i-1);
quicksort(a,i+1,r);
}
}

void button1(int num,bool *state0)
{
if(num>C)
return;
bool * state1;
state1=new bool[N];
for(int i=0;i<N;i++)
{
state1[i]=state0[i];
}
//no change
button2(num,state1);
for(int i=0;i<N;i++)
state1[i]=!state1[i];
button2(num+1,state1);
delete []state1;
}
void button2(int num,bool *state0)
{
if(num>C)
return;
bool * state1;
state1=new bool[N];
for(int i=0;i<N;i++)
{
state1[i]=state0[i];
}
//no change
button3(num,state1);
for(int i=0;i<N;i+=2)
state1[i]=!state1[i];
button3(num+1,state1);
delete [] state1;
}

void button3(int num,bool *state0)
{
if(num>C)
return;
bool * state1;
state1=new bool[N];
for(int i=0;i<N;i++)
{
state1[i]=state0[i];
}
//no change
button4(num,state1);
for(int i=1;i<N;i+=2)
state1[i]=!state1[i];
button4(num+1,state1);
delete [] state1;
}
void button4(int num,bool *state0)
{
if(num>C)
return;
bool * state1;
state1=new bool[N];
for(int i=0;i<N;i++)
{
state1[i]=state0[i];
}
//no change
check(num,state1);
for(int i=0;i<N;i+=3)
state1[i]=!state1[i];
check(num+1,state1);
delete [] state1;
}
void check(int num ,bool *state0)
{
if(num>C)
return;
if((num%2)!=C%2)
return;
for(int i=0;i<N&&final_on[i]!=-2;i++)
{
if(!state0[final_on[i]%6])
{

return ;
}
}
for(int i=0;i<N&&final_off[i]!=-2;i++)
{
if(state0[final_off[i]%6])
{

return ;
}
}
bool *res=new bool[N];
for(int i=0;i<N;i++)
res[i]=state0[i];
result.push_back(res);

}`

+ 订阅