2.1 castle, frac1

4 files changed, 219 insertions, 0 deletions

diff --git a/2.1/castle.c b/2.1/castle.c
new file mode 100644
index 0000000..3ac393c
--- /dev/null
+++ b/2.1/castle.c
@@ -0,0 +1,149 @@
+/*
+ID: mytbk921
+LANG: C
+TASK: castle
+*/
+
+#include <stdio.h>
+#include <string.h>
+
+struct module
+{
+	int component;
+	unsigned char walls;
+};
+
+struct wall
+{
+	int x, y;
+	char dir;
+	int comp[2];
+};
+
+struct module castle[50][50];
+int col, row;
+
+#define FILL(i, j, c) castle[i][j].component=c;flood_fill(i,j);
+
+void flood_fill(int i, int j)
+{
+	unsigned char w = castle[i][j].walls;
+	int c = castle[i][j].component;
+
+	if (j>0 && (w&1)==0 && castle[i][j-1].component==-1) {
+		FILL(i, j-1, c);
+	}
+
+	if (i>0 && (w&2)==0 && castle[i-1][j].component==-1) {
+		FILL(i-1, j, c);
+	}
+
+	if (j<col-1 && (w&4)==0 && castle[i][j+1].component==-1) {
+		FILL(i, j+1, c);
+	}
+
+	if (i<row-1 && (w&8)==0 && castle[i+1][j].component==-1) {
+		FILL(i+1, j, c);
+	}
+}
+
+int main()
+{
+	int i, j;
+	int ncomp;
+	int comp_area[2500];
+	int max_area;
+	int nwalls = 0;
+	struct wall walls[10000];
+	int max_area_created;
+	int wall_to_break;
+
+	FILE *fin = fopen("castle.in", "r");
+	FILE *fout = fopen("castle.out", "w");
+
+	fscanf(fin, "%d%d", &col, &row);
+	for (i=0; i<row; i++) {
+		for (j=0; j<col; j++) {
+			fscanf(fin, "%hhd", &castle[i][j].walls);
+			castle[i][j].component = -1;
+		}
+	}
+	fclose(fin);
+
+	/* step 1: flood fill */
+	ncomp = 0;
+	for (i=0; i<row; i++) {
+		for (j=0; j<col; j++) {
+			if (castle[i][j].component == -1) {
+				castle[i][j].component = ncomp;
+				flood_fill(i, j);
+				ncomp++;
+			}
+		}
+	}
+
+	memset(comp_area, 0, sizeof(int)*ncomp);
+	for (i=0; i<row; i++) {
+		for (j=0; j<col; j++) {
+			comp_area[castle[i][j].component]++;
+		}
+	}
+	max_area = comp_area[0];
+	for (i=0; i<ncomp; i++) {
+		if (comp_area[i]>max_area)
+			max_area = comp_area[i];
+	}
+	fprintf(fout, "%d\n%d\n", ncomp, max_area);
+
+	/* step 2: find all the walls */
+	for (i=0; i<row; i++) {
+		for (j=0; j<col; j++) {
+			int w = castle[i][j].walls;
+			if (j<col-1 && (w&4)) {
+				walls[nwalls].comp[0] = castle[i][j].component;
+				walls[nwalls].comp[1] = castle[i][j+1].component;
+				if (walls[nwalls].comp[0] != walls[nwalls].comp[1]) {
+					walls[nwalls].x = i+1;
+					walls[nwalls].y = j+1;
+					walls[nwalls].dir = 'E';
+					nwalls++;
+				}
+			}
+
+			if (i>0 && (w&2)) {
+				walls[nwalls].comp[0] = castle[i][j].component;
+				walls[nwalls].comp[1] = castle[i-1][j].component;
+				if (walls[nwalls].comp[0] != walls[nwalls].comp[1]) {
+					walls[nwalls].x = i+1;
+					walls[nwalls].y = j+1;
+					walls[nwalls].dir = 'N';
+					nwalls++;
+				}
+			}
+		}
+	}
+
+	max_area_created = -1;
+	for (i=0; i<nwalls; i++) {
+		int area = comp_area[walls[i].comp[0]] + comp_area[walls[i].comp[1]];
+		if (area > max_area_created) {
+			max_area_created = area;
+			wall_to_break = i;
+		} else if (area == max_area_created) {
+			if (walls[i].y < walls[wall_to_break].y)
+				wall_to_break = i;
+			else if (walls[i].y == walls[wall_to_break].y
+						&& walls[i].x > walls[wall_to_break].x)
+				wall_to_break = i;
+			else if (walls[i].y == walls[wall_to_break].y
+						&& walls[i].x == walls[wall_to_break].x
+						&& walls[i].dir == 'N')
+				wall_to_break = i;
+		}
+	}
+	fprintf(fout, "%d\n%d %d %c\n", max_area_created,
+			  walls[wall_to_break].x, walls[wall_to_break].y,
+			  walls[wall_to_break].dir);
+	fclose(fout);
+	return 0;
+}
diff --git a/2.1/castle.in.0 b/2.1/castle.in.0
new file mode 100644
index 0000000..416dac0
--- /dev/null
+++ b/2.1/castle.in.0
@@ -0,0 +1,5 @@
+7 4
+11 6 11 6 3 10 6
+7 9 6 13 5 15 5
+1 10 12 7 13 7 5
+13 11 10 8 10 12 13
diff --git a/2.1/castle.in.1 b/2.1/castle.in.1
new file mode 100644
index 0000000..ddf422a
--- /dev/null
+++ b/2.1/castle.in.1
@@ -0,0 +1,6 @@
+5 5
+3 2 6 3 6
+1 8 4 1 4
+13 7 13 9 4
+3 0 2 6 5
+9 8 8 12 13
diff --git a/2.1/frac1.c b/2.1/frac1.c
new file mode 100644
index 0000000..1901abc
--- /dev/null
+++ b/2.1/frac1.c
@@ -0,0 +1,59 @@
+/*
+ID: mytbk921
+LANG: C
+TASK: frac1
+*/
+
+#include <stdio.h>
+#include <stdlib.h>
+
+struct rational
+{
+	int numer, denom;
+};
+
+int comp(const void *s, const void *t)
+{
+	const struct rational *r1 = (struct rational*)s;
+	const struct rational *r2 = (struct rational*)t;
+	return r1->numer*r2->denom - r2->numer*r1->denom;
+}
+
+int gcd(int x, int y)
+{
+	if (y==0)
+		return x;
+	else
+		return gcd(y, x%y);
+}
+
+struct rational fracs[40000];
+int nfrac;
+
+int main()
+{
+	FILE *fin = fopen("frac1.in", "r");
+	FILE *fout = fopen("frac1.out", "w");
+
+	int N;
+	int i, j;
+	fscanf(fin, "%d", &N);
+	fclose(fin);
+
+	nfrac = 0;
+	for (i=1; i<=N; i++) {
+		for (j=1; j<i; j++) {
+			if (gcd(i, j)==1) {
+				fracs[nfrac].denom = i;
+				fracs[nfrac].numer = j;
+				nfrac++;
+			}
+		}
+	}
+	qsort(fracs, nfrac, sizeof(fracs[0]), comp);
+	fprintf(fout, "0/1\n");
+	for (i=0; i<nfrac; i++)
+		fprintf(fout, "%d/%d\n", fracs[i].numer, fracs[i].denom);
+	fprintf(fout, "1/1\n");
+	return 0;
+}