finish 2.1

3 files changed, 208 insertions, 0 deletions

diff --git a/2.1/hamming.c b/2.1/hamming.c
new file mode 100644
index 0000000..abc3483
--- /dev/null
+++ b/2.1/hamming.c
@@ -0,0 +1,75 @@
+/*
+ID: mytbk921
+LANG: C
+TASK: hamming
+*/
+
+#include <stdio.h>
+
+typedef unsigned char u8;
+
+static unsigned
+popcount(unsigned x)
+{
+	unsigned c = 0;
+	while (x) {
+		if (x&1) c++;
+		x >>= 1;
+	}
+	return c;
+}
+
+static unsigned
+hamdist(unsigned x, unsigned y)
+{
+	return popcount(x^y);
+}
+
+u8 s[64];
+int N, B, D;
+
+int search(int i)
+{
+	int t, j;
+	if (i==N) return 1;
+
+	for (t=s[i-1]+1; t<(1<<B); t++) {
+		for (j=0; j<i; j++) {
+			if (hamdist(s[j], t)<D)
+				break;
+		}
+		if (j==i) {
+			s[j] = t;
+			if (search(i+1))
+				return 1;
+		}
+	}
+	/* all searched */
+	return 0;
+}
+
+int main()
+{
+	int i;
+
+	FILE *fin = fopen("hamming.in", "r");
+	FILE *fout = fopen("hamming.out", "w");
+	fscanf(fin, "%d%d%d", &N, &B, &D);
+	fclose(fin);
+
+	s[0] = 0;
+	if (search(1)) {
+		for (i=0; i<N; i++) {
+			if (i%10==0) {
+				if (i>0)
+					fprintf(fout, "\n");
+			} else {
+				fprintf(fout, " ");
+			}
+			fprintf(fout, "%d", s[i]);
+		}
+		fprintf(fout, "\n");
+	}
+	fclose(fout);
+	return 0;
+}
diff --git a/2.1/holstein.c b/2.1/holstein.c
new file mode 100644
index 0000000..637a43a
--- /dev/null
+++ b/2.1/holstein.c
@@ -0,0 +1,78 @@
+/*
+ID: mytbk921
+LANG: C
+TASK: holstein
+*/
+
+#include <stdio.h>
+#include <string.h>
+#include <math.h>
+#include <stdlib.h>
+
+int vitamins[25];
+int feeds[15][25];
+int nv;
+int nf;
+
+static unsigned
+popcount(unsigned x)
+{
+	unsigned c = 0;
+	while (x) {
+		if (x&1) c++;
+		x >>= 1;
+	}
+	return c;
+}
+
+int main()
+{
+	FILE *fin = fopen("holstein.in", "r");
+	FILE *fout = fopen("holstein.out", "w");
+	int i, j;
+	unsigned scm, best, ans_n, tn;
+	int tmp_v[25];
+
+	fscanf(fin, "%d", &nv);
+	for (i=0; i<nv; i++)
+		fscanf(fin, "%d", &vitamins[i]);
+	fscanf(fin, "%d", &nf);
+	for (j=0; j<nf; j++) {
+		for (i=0; i<nv; i++)
+			fscanf(fin, "%d", &feeds[j][i]);
+	}
+
+	/* init: use all feeds */
+	best = (1<<nf)-1;
+	ans_n = nf;
+
+	for (scm=1; scm<(1<<nf)-1; scm++) {
+		tn = popcount(scm);
+		if (tn>=ans_n)
+			continue;
+		memset(tmp_v, 0, sizeof(tmp_v));
+		for (i=0; i<nf; i++) {
+			if (scm&(1<<i)) {
+				for (j=0; j<nv; j++)
+					tmp_v[j] += feeds[i][j];
+			}
+		}
+		for (i=0; i<nv; i++) {
+			if (tmp_v[i]<vitamins[i])
+				break;
+		}
+		if (i==nv) {
+			best = scm;
+			ans_n = tn;
+		}
+	}
+
+	fprintf(fout, "%d", ans_n);
+	for (i=0; i<nf; i++) {
+		if (best&(1<<i))
+			fprintf(fout, " %d", i+1);
+	}
+	fprintf(fout, "\n");
+	fclose(fout);
+	return 0;
+}
diff --git a/2.1/sort3.c b/2.1/sort3.c
new file mode 100644
index 0000000..fe709bb
--- /dev/null
+++ b/2.1/sort3.c
@@ -0,0 +1,55 @@
+/*
+ID: mytbk921
+LANG: C
+TASK: sort3
+*/
+
+#include <stdio.h>
+#include <string.h>
+#include <math.h>
+#include <stdlib.h>
+
+static inline int min(int a, int b) { return a<b?a:b; }
+
+int main()
+{
+	FILE *fin = fopen("sort3.in", "r");
+	FILE *fout = fopen("sort3.out", "w");
+	int N;
+	int a[1000];
+	int count[3];
+	int mat[3][3];
+	int i;
+	int nswaps;
+
+	memset(count, 0, sizeof(count));
+	memset(mat, 0, sizeof(mat));
+
+	fscanf(fin, "%d", &N);
+	for (i=0; i<N; i++)
+		fscanf(fin, "%d", &a[i]);
+	fclose(fin);
+
+	for (i=0; i<N; i++) {
+		a[i]--;
+		count[a[i]]++;
+	}
+
+	for (i=0; i<count[0]; i++)
+		mat[a[i]][0]++;
+
+	for (; i<count[0]+count[1]; i++)
+		mat[a[i]][1]++;
+
+	for (; i<N; i++)
+		mat[a[i]][2]++;
+
+	nswaps = min(mat[0][1], mat[1][0]) + min(mat[0][2], mat[2][0]) +
+		min(mat[1][2], mat[2][1]) +
+		(abs(mat[0][1]-mat[1][0]) +
+		 abs(mat[0][2]-mat[2][0]) +
+		 abs(mat[1][2]-mat[2][1])) / 3 * 2;
+	fprintf(fout, "%d\n", nswaps);
+	fclose(fout);
+	return 0;
+}