summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
-rw-r--r--2.1/hamming.c75
-rw-r--r--2.1/holstein.c78
-rw-r--r--2.1/sort3.c55
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;
+}