summaryrefslogtreecommitdiff
path: root/2.2/lamps.c
diff options
context:
space:
mode:
Diffstat (limited to '2.2/lamps.c')
-rw-r--r--2.2/lamps.c139
1 files changed, 139 insertions, 0 deletions
diff --git a/2.2/lamps.c b/2.2/lamps.c
new file mode 100644
index 0000000..03422ad
--- /dev/null
+++ b/2.2/lamps.c
@@ -0,0 +1,139 @@
+/*
+ID: mytbk921
+LANG: C
+TASK: lamps
+*/
+
+#include <stdio.h>
+#include <string.h>
+
+static int popcount(unsigned int i)
+{
+ int s = 0;
+ while (i) {
+ if (i&1)
+ s++;
+ i >>= 1;
+ }
+ return s;
+}
+
+int n,c,on[101],off[101],final[101];
+int result[16][100];
+int nres;
+int sorted[16];
+
+int comp(int i, int j)
+{
+ int k;
+ for (k=1; k<=n; k++) {
+ if (result[i][k] < result[j][k])
+ return -1;
+ if (result[i][k] > result[j][k])
+ return 1;
+ }
+ return 0;
+}
+
+int main()
+{
+ FILE *fin = fopen("lamps.in", "r");
+ FILE *fout = fopen("lamps.out", "w");
+
+ int l;
+ int i,j,k,pc,tmp;
+
+ fscanf(fin, "%d%d", &n, &c);
+ memset(on, 0, sizeof(on));
+ memset(off, 0, sizeof(off));
+ while (1) {
+ fscanf(fin, "%d", &l);
+ if (l!=-1)
+ on[l] = 1;
+ else
+ break;
+ }
+ while (1) {
+ fscanf(fin, "%d", &l);
+ if (l!=-1) {
+ if (on[l])
+ goto Impossible;
+ off[l] = 1;
+ } else {
+ break;
+ }
+ }
+ fclose(fin);
+
+ nres = 0;
+ for (i=0; i<16; i++) {
+ pc = popcount(i);
+ if (pc>c || pc%2 != c%2)
+ continue;
+ if (i&1) {
+ for (j=1; j<=n; j++)
+ final[j] = 0;
+ } else {
+ for (j=1; j<=n; j++)
+ final[j] = 1;
+ }
+ if (i&2) {
+ for (j=1; j<=n; j+=2)
+ final[j] = 1-final[j];
+ }
+ if (i&4) {
+ for (j=2; j<=n; j+=2)
+ final[j] = 1-final[j];
+ }
+ if (i&8) {
+ for (j=1; j<=n; j+=3)
+ final[j] = 1-final[j];
+ }
+ for (j=1; j<=n; j++) {
+ if ((on[j]&&!final[j]) || (off[j]&&final[j]))
+ break;
+ }
+ if (j>n) {
+ for (j=1; j<=n; j++)
+ result[nres][j] = final[j];
+ nres++;
+ }
+ }
+
+ if (nres==0)
+ goto Impossible;
+
+ for (i=0; i<nres; i++)
+ sorted[i] = i;
+
+ /* do an insertion sort */
+ for (i=1; i<nres; i++) {
+ for (j=0; j<i; j++) {
+ tmp = comp(sorted[j], sorted[i]);
+ if (tmp==0)
+ sorted[i] = sorted[j];
+ if (tmp>=0) {
+ tmp = sorted[i];
+ for (k=i; k>j; k--)
+ sorted[k] = sorted[k-1];
+ sorted[j] = tmp;
+ break;
+ }
+ }
+ }
+
+ for (i=0; i<nres; i++) {
+ if (i==0 || sorted[i]!=sorted[i-1]) {
+ for (j=1; j<=n; j++)
+ fprintf(fout, "%d", result[sorted[i]][j]);
+
+ fprintf(fout, "\n");
+ }
+ }
+ fclose(fout);
+ return 0;
+Impossible:
+ fprintf(fout, "IMPOSSIBLE\n");
+ fclose(fout);
+ return 0;
+}