diff options
| -rw-r--r-- | 2.1/hamming.c | 75 | ||||
| -rw-r--r-- | 2.1/holstein.c | 78 | ||||
| -rw-r--r-- | 2.1/sort3.c | 55 |
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; +} |