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:
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.
If there are no possible configurations, output a single line with the single word `IMPOSSIBLE'
总共就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种~~枚举出这些情况..当且仅当当前所案件的次数与所需要的按键次数之差为偶数(不断地来回按)并且得到的情况是满足输入的要求的就找到了一个~~
https://github.com/TomConerly/Competition-Programming/blob/master/USACO/Chapter2/lamps.java
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/
http://lsharemy.com/wordpress/index.php/csit/usaco-prob-party-lamps/
Read full article from 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,...
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 -1In 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 0110110110In 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.
总共就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
