2.2 subset, runround, lamps

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;
+}