diff options
Diffstat (limited to '2.2/lamps.c')
-rw-r--r-- | 2.2/lamps.c | 139 |
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; +} |