summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
-rw-r--r--2.2/lamps.c139
-rw-r--r--2.2/runround.c72
-rw-r--r--2.2/subset.c50
3 files changed, 261 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;
+}
diff --git a/2.2/runround.c b/2.2/runround.c
new file mode 100644
index 0000000..498b579
--- /dev/null
+++ b/2.2/runround.c
@@ -0,0 +1,72 @@
+/*
+ID: mytbk921
+LANG: C
+TASK: runround
+*/
+
+#include <stdio.h>
+#include <stdlib.h>
+
+int runround(unsigned int x)
+{
+ unsigned int msd, lsd, last, t;
+ int next[10];
+ int map[10];
+ int i;
+
+ for (i=0; i<10; i++) map[i] = 0;
+
+ lsd = x % 10;
+ if (lsd == 0) return 0;
+ last = lsd;
+ map[lsd] = 1;
+ x /= 10;
+ while (x>=10) {
+ t = x % 10;
+ if (map[t] || t==0) return 0;
+ map[t] = 1;
+ next[t] = last;
+ last = t;
+ x /= 10;
+ }
+ msd = x;
+ map[msd] = 1;
+ next[msd] = last;
+ next[lsd] = msd;
+
+ last = msd;
+ do {
+ if (map[last])
+ map[last] = 0;
+ else
+ return 0;
+ t = last;
+ for (i=0; i<t; i++)
+ last = next[last];
+ } while (last != msd);
+ for (i=0; i<10; i++) {
+ if (map[i])
+ return 0;
+ }
+ return 1;
+}
+
+int main()
+{
+ FILE *fin = fopen("runround.in", "r");
+ FILE *fout = fopen("runround.out", "w");
+
+ unsigned int m;
+ fscanf(fin, "%u", &m);
+ fclose(fin);
+
+ while (1) {
+ m++;
+ if (runround(m)) {
+ fprintf(fout, "%u\n", m);
+ fclose(fout);
+ return 0;
+ }
+ }
+ return 0;
+}
diff --git a/2.2/subset.c b/2.2/subset.c
new file mode 100644
index 0000000..9f05b2c
--- /dev/null
+++ b/2.2/subset.c
@@ -0,0 +1,50 @@
+/*
+ID: mytbk921
+LANG: C
+TASK: subset
+*/
+
+#include <stdio.h>
+#include <stdlib.h>
+
+int main()
+{
+ FILE *fin = fopen("subset.in", "r");
+ FILE *fout = fopen("subset.out", "w");
+
+ long long dp[40][500];
+ int N, sum;
+ int i, j;
+ fscanf(fin, "%d", &N);
+ fclose(fin);
+
+ sum = N*(N+1)/2;
+ if (sum%2) {
+ fprintf(fout, "0\n");
+ fclose(fout);
+ return 0;
+ }
+ sum /= 2;
+
+ /* dp[x][y]: number of sets that sum of set is y
+ * with all numbers in the set <=x
+ *
+ * dp[k][0] = 1
+ * dp[0][k] = 0 for k>0
+ */
+ for (i=0; i<=N; i++)
+ dp[i][0] = 1;
+ for (i=1; i<=sum; i++)
+ dp[0][i] = 0;
+ for (i=1; i<=N; i++) {
+ for (j=1; j<=sum; j++) {
+ if (j<i)
+ dp[i][j] = dp[j][j];
+ else
+ dp[i][j] = dp[i-1][j] + dp[i-1][j-i];
+ }
+ }
+ fprintf(fout, "%lld\n", dp[N][sum]/2);
+ fclose(fout);
+ return 0;
+}