summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorIru Cai <mytbk920423@gmail.com>2018-04-17 16:34:59 +0800
committerIru Cai <mytbk920423@gmail.com>2018-04-17 16:54:50 +0800
commit8482680ad68093fa56d10364f591764250c0c2f0 (patch)
tree5189995ce81a4ff7af17ec9f6d8f685297bcf81d
parent235aef5fae393c738e78a5b188051557b6ebd97c (diff)
downloadusaco-8482680ad68093fa56d10364f591764250c0c2f0.tar.xz
2.1 castle, frac1
-rw-r--r--2.1/castle.c149
-rw-r--r--2.1/castle.in.05
-rw-r--r--2.1/castle.in.16
-rw-r--r--2.1/frac1.c59
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;
+}