Party Lamps - USACO 2.2.4

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

TODO - http://qingtangpaomian.iteye.com/blog/1635377
总共就4个按钮...如果我1,2,3,4都按过一次了..再按一下1 or 2 or 3 or 4灯的情况不和只按了2,3,4 or 1,3,4 or 1,2,4 or  1,2,3一样吗?因为一个按钮按两次就相当于没按..那么实际上能出现的最多情况也就是C(1,4)+C(2,4)+C(3,4)+C(4,4)=17种~~枚举出这些情况..当且仅当当前所案件的次数与所需要的按键次数之差为偶数(不断地来回按)并且得到的情况是满足输入的要求的就找到了一个~~

这道题目还是暴力枚举，开关按两次以后等于没有按。如果同时按了偶数和奇数按钮等于按了一号按钮，按了一号和偶数等于按了奇数按钮，按了一号和奇数按钮等于按了偶数按钮。

那么无论怎么枚举按钮只可能出现以下8种情况：1.什么都没有按；2.只按了一号按钮；3.只按了奇数按钮；4.只按了偶数按钮；5.只按了3*k+1按钮；6.同时按了一号按钮和3*k+1按钮；7.同时按了奇数按钮和3*k+1按钮；8.同时按了偶数按钮和3*k+1按钮

由于只有以上的8种状态，现在难点就在于如何将这些状态与cnt（按了几次）对应起来。

 分析后，我们可以对cnt做如下分类：1. cnt ==0 ;2.cnt ==1；3.cnt==2 ；4.cnt==3；5.cnt>=4，并且cnt为偶数 ;6.cnt>4，并且cnt为奇数

cnt的前四种情况都比较简单，可以直接模拟出。现在讨论第5种和第6种情况，第5种情况等价于cnt==4的情况（因为最多有四个开关，所以cnt>4的时候一定可以找到两个开关作用两两相消除），第6种情况等价于cnt==3（原理同上）。

按照上面说明的情况，我们只需要对输入的cnt进行判断的，然后将该情况可能产生的亮灯状态与输入的开关灯状态比较，如果满足则输出。

https://github.com/TomConerly/Competition-Programming/blob/master/USACO/Chapter2/lamps.java

	public static void main(String[] args) throws IOException {
	Scanner sc = new Scanner(new File("lamps.in"));
	PrintWriter out = new PrintWriter(new BufferedWriter(new FileWriter("lamps.out")));
	int N = sc.nextInt();
	int C = sc.nextInt();
	ArrayList<Integer> setOn = new ArrayList<Integer>();
	while(true)
	{
	int temp = sc.nextInt();
	if(temp == -1) break;
	setOn.add(temp-1);
	}
	ArrayList<Integer> setOff = new ArrayList<Integer>();
	while(true)
	{
	int temp = sc.nextInt();
	if(temp == -1) break;
	setOff.add(temp-1);
	}
	boolean[] lights = new boolean[N];
	Arrays.fill(lights,true);
	r = new boolean[2][2][2][2][N];
	r[0][0][0][0] = lights;
	r[0][0][0][1] = move1(lights);
	r[0][0][1][0] = move2(lights);
	r[0][1][0][0] = move3(lights);
	r[1][0][0][0] = move4(lights);
	r[0][0][1][1] = move1(move2(lights));
	r[0][1][0][1] = move1(move3(lights));
	r[1][0][0][1] = move1(move4(lights));
	r[0][1][1][0] = move2(move3(lights));
	r[1][0][1][0] = move2(move4(lights));
	r[1][1][0][0] = move3(move4(lights));
	r[1][1][1][0] = move2(move3(move4(lights)));
	r[1][1][0][1] = move1(move3(move4(lights)));
	r[1][0][1][1] = move1(move1(move4(lights)));
	r[0][1][1][1] = move1(move2(move3(lights)));
	r[1][1][1][1] = move1(move2(move3(move4(lights))));
	ArrayList<Answer> list = new ArrayList<Answer>();
	for(int i = 0; i < 2;i++)
	{
	for(int j = 0; j < 2;j++)
	{
	for(int k = 0; k < 2;k++)
	{
	for(int m = 0; m < 2;m++)
	{
	if(C-i-j-k-m >= 0 && (C-i-j-k-m)%2 == 0)
	{
	boolean legal = true;
	for(int on:setOn)
	{
	if(!r[i][j][k][m][on])legal = false;
	}
	for(int off:setOff)
	{
	if(r[i][j][k][m][off])legal = false;
	}
	if(legal) list.add(new Answer(i,j,k,m));
	}
	}
	}
	}
	}
	Collections.sort(list);
	for(Answer a: list)
	{
	out.println(a.toString());
	}
	if(list.size() == 0)
	out.println("IMPOSSIBLE");
	out.close();
	}
	static boolean[][][][][] r;
	private static class Answer implements Comparable<Answer>
	{
	int i,j,k,m;
	public Answer(int a, int b, int c, int d)
	{
	i=a;
	j=b;
	k=c;
	m=d;
	}
	public int compareTo(Answer a) {
	for(int t = 0; t < r[0][0][0][0].length;t++)
	{
	if(r[i][j][k][m][t] && !r[a.i][a.j][a.k][a.m][t]) return 1;
	if(!r[i][j][k][m][t] && r[a.i][a.j][a.k][a.m][t]) return -1;
	}
	return 0;
	}
	public String toString()
	{
	String out = "";
	for(int t = 0; t < r[0][0][0][0].length;t++)
	{
	if(r[i][j][k][m][t]) out = out+"1";
	else out = out+"0";
	}
	return out;
	}
	}
	public static boolean[] move1(boolean[] in)
	{
	boolean[] ret = new boolean[in.length];
	for(int i = 0; i < ret.length;i++)
	{
	ret[i] = !in[i];
	}
	return ret;
	}
	public static boolean[] move2(boolean[] in)
	{
	boolean[] ret = new boolean[in.length];
	for(int i = 0; i < ret.length;i++)
	{
	if(i%2 == 1)
	ret[i] = !in[i];
	else
	ret[i] = in[i];
	}
	return ret;
	}
	public static boolean[] move3(boolean[] in)
	{
	boolean[] ret = new boolean[in.length];
	for(int i = 0; i < ret.length;i++)
	{
	if(i%2 == 0)
	ret[i] = !in[i];
	else
	ret[i] = in[i];
	}
	return ret;
	}
	public static boolean[] move4(boolean[] in)
	{
	boolean[] ret = new boolean[in.length];
	for(int i = 0; i < ret.length;i++)
	{
	if(i%3 == 0)
	ret[i] = !in[i];
	else
	ret[i] = in[i];
	}
	return ret;
	}

http://jackneus.com/programming-archives/party-lamps/
https://www.byvoid.com/blog/usaco-224-party-lamps

X.  Brute Force: 4^C
http://lujunda.cn/2012/08/04/usacosection-2-2%E6%90%9C%E7%B4%A2-party-lamps/

point op(int t,point temp)

//operation操作函数。

//参数t表示按钮编号。

//temp表示按钮作用的对象状态。

{

    if(t==1)

        for(int i=1;i<=n;i++)

            temp.arry[i]=temp.arry[i]-'0'?'0':'1';

    else if(t==2)

        for(int i=1;i<=n;i+=2)

            temp.arry[i]=temp.arry[i]-'0'?'0':'1';

    else if(t==3)

        for(int i=2;i<=n;i+=2)

            temp.arry[i]=temp.arry[i]-'0'?'0':'1';

    else

        for(int i=0;3*i+1<=n;i++)

            temp.arry[3*i+1]=temp.arry[3*i+1]-'0'?'0':'1';

    return temp;

}

bool check(point temp)

//检查temp是否与目标状态相符。

{

    for(int i=1;i<=n;i++)

    {

        if(on[i]&&temp.arry[i]=='0')

            return false;

        if(off[i]&&temp.arry[i]=='1')

            return false;

    }

    string result=temp.arry;

    if(mark[result])

    //检查temp是否与其他已确定的状态相重复。

        return false;

    mark[result]=true;

    return true;

}

void dfs(point temp,int sum)

//利用深搜枚举4^c种状态。

{

    if(sum==c)

    {

        if(check(temp))

            res[total++]=temp;

        return;

    }

    for(int i=1;i<5;i++)

        dfs(op(i,temp),sum+1);

}

http://lsharemy.com/wordpress/index.php/csit/usaco-prob-party-lamps/
Read full article from partylamps - codetrick