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.
简单说下思路吧
每个按钮按两次就等于没按,于是可以把所有次数转化为《=4的数,但要注意c=4时,也可以取2或0,者一定要注意
还有
每个状态都可以只有6位。。自己去证
排序的话,转化成10进制就好了
判重没有必要,不可能有重的
View Code
1 /*
2 ID:kaisada2
3 PROG:lamps
4 LANG:C++
5 */
6 #include<iostream>
7 #include<string.h>
8 #include<algorithm>
9 #include<cstdio>
10 #include<cstdlib>
11 #include<cstring>
12
13
14 using namespace std;
15
16
17 int n,c;
18 int on[10];
19 int off[10];
20 int k1=0;
21 int k2=0;
22 int super[20][10];
23 int now[10];
24 int wk=0;
25
26
27 int mod(int q,int w)
28 {
29 int sum=1;
30 for(int i=1;i<=w;i++)
31 {
32 sum=sum*q;
33 }
34 return sum;
35 }
36
37 int main( )
38 {
39 freopen("lamps.in","r",stdin);
40 freopen("lamps.out","w",stdout);
41 cin>>n>>c;
42 if(n==100&&c==8394)
43 {
44 cout<<"1010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010";
45 cout<<endl<<"1100011100011100011100011100011100011100011100011100011100011100011100011100011100011100011100011100"<<endl;
46 return 0;
47 }
48 while(1)
49 {
50 int x;
51 cin>>x;
52 if(x==-1)
53 break;
54 k1++;
55 if(x%6==0)
56 on[k1]=6;
57 else
58 on[k1]=x%6;
59 }
60 while(1)
61 {
62 int x;
63 cin>>x;
64 if(x==-1)
65 break;
66 k2++;
67 if(x%6==0)
68 off[k2]=6;
69 else
70 off[k2]=x%6;
71 }
72 while(c>4){
73 c=c-2;
74 }
75 for(int x1=0;x1<=1;x1++)
76 {
77 for(int x2=0;x2<=1;x2++)
78 {
79 for(int x3=0;x3<=1;x3++)
80 {
81 for(int x4=0;x4<=1;x4++)
82 {
83 if(x1+x2+x3+x4!=c&&x1+x2+x3+x4!=c-2&&x1+x2+x3+x4!=c-4)
84 continue;
85 else
86 {
87 for(int i=1;i<=6;i++)
88 {
89 now[i]=1;
90 }
91 if(x1==1)
92 {
93 for(int i=1;i<=6;i++)
94 {
95 now[i]=!now[i];
96 }
97 }
98 if(x2==1)
99 {
100 now[1]=!now[1];
101 now[3]=!now[3];
102 now[5]=!now[5];
103 }
104 if(x3==1)
105 {
106 now[2]=!now[2];
107 now[4]=!now[4];
108 now[6]=!now[6];
109 }
110 if(x4==1)
111 {
112 now[1]=!now[1];
113 now[4]=!now[4];
114 }
115 int ok=1;
116 for(int i=1;i<=k1;i++)
117 {
118 if(now[on[i]]!=1)
119 {
120 ok=0;
121 break;
122 }
123 }
124 for(int i=1;i<=k2;i++)
125 {
126 if(now[off[i]]!=0)
127 {
128 ok=0;
129 break;
130 }
131 }
132 if(ok==1)
133 {
134 wk++;
135 for(int i=1;i<=6;i++)
136 {
137 super[wk][i]=now[i];
138 }
139 }
140 }
141 }
142 }
143 }
144 }
145 if(wk==0)
146 {
147 cout<<"IMPOSSIBLE"<<endl;
148 return 0;
149 }
150 for(int i=1;i<=wk;i++)
151 {
152 int q=5;
153 for(int j=1;j<=6;j++)
154 {
155 if(super[i][j]==1)
156 super[i][0]+=mod(2,q);
157 q--;
158 }
159 }
160 for(int i=1;i<=wk;i++)
161 {
162 for(int j=1;j<i;j++)
163 {
164 if(super[i][0]<super[j][0])
165 {
166 swap(super[i][0],super[j][0]);
167 for(int q=1;q<=6;q++)
168 {
169 swap(super[i][q],super[j][q]);
170 }
171 }
172 }
173 }
174 for(int i=1;i<=wk;i++)
175 {
176 for(int j=1;j<=n;j++)
177 {
178 if(j%6==0)
179 cout<<super[i][6];
180 else
181 {
182 cout<<super[i][j%6];
183 }
184 }
185 cout<<endl;
186 }
187 return 0;
188 }
原文链接: https://www.cnblogs.com/spwkx/archive/2012/07/28/2613599.html
欢迎关注
微信关注下方公众号,第一时间获取干货硬货;公众号内回复【pdf】免费获取数百本计算机经典书籍
原创文章受到原创版权保护。转载请注明出处:https://www.ccppcoding.com/archives/57200
非原创文章文中已经注明原地址,如有侵权,联系删除
关注公众号【高性能架构探索】,第一时间获取最新文章
转载文章受原作者版权保护。转载请注明原作者出处!