From 775d3113cb90a3300eb2261842290f0884db420b Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?Anton=20Luka=20=C5=A0ijanec?= Date: Fri, 18 Nov 2022 19:10:40 +0100 Subject: 1. liga zotks --- .gitignore | 1 + inf/lige/1/.gitignore | 1 + inf/lige/1/1.c | 50 +++++++++++++++++++++++++++ inf/lige/1/1.txt | 6 ++++ inf/lige/1/2.c | 70 ++++++++++++++++++++++++++++++++++++++ inf/lige/1/2.txt | 5 +++ inf/lige/1/3.c | 52 ++++++++++++++++++++++++++++ inf/lige/1/3.txt | 17 ++++++++++ inf/lige/1/4.c | 94 +++++++++++++++++++++++++++++++++++++++++++++++++++ inf/lige/1/4.txt | 7 ++++ 10 files changed, 303 insertions(+) create mode 100644 inf/lige/1/.gitignore create mode 100644 inf/lige/1/1.c create mode 100644 inf/lige/1/1.txt create mode 100644 inf/lige/1/2.c create mode 100644 inf/lige/1/2.txt create mode 100644 inf/lige/1/3.c create mode 100644 inf/lige/1/3.txt create mode 100644 inf/lige/1/4.c create mode 100644 inf/lige/1/4.txt diff --git a/.gitignore b/.gitignore index 31500ee..e317e69 100644 --- a/.gitignore +++ b/.gitignore @@ -6,3 +6,4 @@ core \#*.lyx# .RData .Rhistory +*.out diff --git a/inf/lige/1/.gitignore b/inf/lige/1/.gitignore new file mode 100644 index 0000000..323c637 --- /dev/null +++ b/inf/lige/1/.gitignore @@ -0,0 +1 @@ +naloge.tar diff --git a/inf/lige/1/1.c b/inf/lige/1/1.c new file mode 100644 index 0000000..8bbfdaa --- /dev/null +++ b/inf/lige/1/1.c @@ -0,0 +1,50 @@ +#include +#include +#include +int main () { + int debug = 0; + char buf[128]; + char buf2[128]; + fgets(buf, 128, stdin); + char * x = buf; + int m = strtol(x, &x, 10); + x++; + int n = strtol(x, NULL, 10); + if (debug) fprintf(stderr, "m %d n %d\n", m, n); + char * old = buf; + char * cur = buf2; + memset(old, '0', 128); + memset(cur, '0', 128); + unsigned mej = 0; + while (!ferror(stdin) && !feof(stdin) && m--) { + fgets(cur, 128, stdin); + unsigned meja = 0; + for (int i = 0; i < n-1; i++) + if (cur[i] != cur[i+1]) + meja++; + if (cur[n-1] == '1') + meja++; + if (cur[0] == '1') + meja++; + if (debug) fprintf(stderr, "vrsta. po ld je mej: %u\n", meja); + mej += meja; + meja = 0; + for (int i = 0; i < n; i++) + if (old[i] != cur[i]) + meja++; + if (debug) fprintf(stderr, "\tpo gor dol je mej: %u\n", meja); + mej += meja; + meja = 0; + if (!m) + for (int i = 0; i < n; i++) + if (cur[i] == '1') + meja++; + if (debug) fprintf(stderr, "\tpo zadnji je mej: %u\n", meja); + mej += meja; + meja = 0; + char * tmp = old; + old = cur; + cur = tmp; + } + printf("%u\n", mej); +} diff --git a/inf/lige/1/1.txt b/inf/lige/1/1.txt new file mode 100644 index 0000000..4792ef4 --- /dev/null +++ b/inf/lige/1/1.txt @@ -0,0 +1,6 @@ +5 12 +000111000100 +010000001111 +001010001101 +001110000111 +000000000000 diff --git a/inf/lige/1/2.c b/inf/lige/1/2.c new file mode 100644 index 0000000..b961093 --- /dev/null +++ b/inf/lige/1/2.c @@ -0,0 +1,70 @@ +#include +#include +#include +int main (void) { + char buf[128]; + fgets(buf, 128, stdin); + char * c = buf; + int n = strtol(c, &c, 10); + c++; + int k = strtol(c, &c, 10); + int * zx = calloc(1000000, sizeof *zx); + int * zy = calloc(1000000, sizeof *zy); + int x = 0; + int y = 0; + int num = 0; + int vseh = 0; + while (1) { + char a = getchar(); + switch (a) { + case EOF: + goto x; + case '\r': + break; + case '\n': +#ifndef EVAL + fprintf(stderr, "newline\n"); +#endif + if (num) { + zx[num-1] = x; + zy[num-1] = y; + num = 0; + vseh++; + } + x = 0; + y++; + break; + case ' ': +#ifndef EVAL + fprintf(stderr, "presledek\n"); +#endif + if (num) { + zx[num-1] = x; + zy[num-1] = y; + num = 0; + vseh++; + } + x++; + break; + default: +#ifndef EVAL + fprintf(stderr, "številka %c\n", a); +#endif + num *= 10; + num += a - '0'; + } + } +x:; + long long int sum = 0; + int curx = 0; + int cury = 0; + for (int i = 0; i < vseh; i++) { + sum += abs(curx - zx[i]) + abs(cury - zy[i]); +#ifndef EVAL + fprintf(stderr, "znamenitost %d je na %d %d, sum je %lld\n", i, zx[i], zy[i], sum); +#endif + curx = zx[i]; + cury = zy[i]; + } + printf("%lld\n", sum); +} diff --git a/inf/lige/1/2.txt b/inf/lige/1/2.txt new file mode 100644 index 0000000..d597a51 --- /dev/null +++ b/inf/lige/1/2.txt @@ -0,0 +1,5 @@ +4 3 +0 0 0 0 +0 0 2 0 +0 3 0 0 +0 0 0 1 diff --git a/inf/lige/1/3.c b/inf/lige/1/3.c new file mode 100644 index 0000000..ff62f33 --- /dev/null +++ b/inf/lige/1/3.c @@ -0,0 +1,52 @@ +#include +#include +#include +int main (void) { + char buf[128]; + fgets(buf, 128, stdin); + int p = atoi(buf); + int * c = calloc(10000, sizeof *c); + while (p--) { + fgets(buf, 128, stdin); + int n = atoi(buf); + int i = n; + int sum = 0; + while (i--) { + fgets(buf, 128, stdin); + c[i] = atoi(buf); + sum += c[i]; + if (!c[i]) + while (1); + } + long double avg = (long double) sum/n; +#ifndef EVAL + fprintf(stderr, "primer %d ima %d števil, katerih avg je %Lf\n", p, n, avg); +#endif + for (int i = 0; i < n-1; i++) { + if (c[i] == -1) + continue; + if (c[i] == avg) + continue; + for (int j = i+1; j < n; j++) { + if (c[j] == avg) + continue; + if (c[j] == -1) + continue; +#ifndef EVAL + fprintf(stderr, "avg %d in %d je %Lf\n", c[i], c[j], (long double) (c[i]+c[j])/2); +#endif + if ((long double) (c[i]+c[j])/2 == avg) { + c[i] = -1; + c[j] = -1; + break; + } + if (j == n-1) + goto bail; + } + } + printf("DA\n"); + continue; +bail: + printf("NE\n"); + } +} diff --git a/inf/lige/1/3.txt b/inf/lige/1/3.txt new file mode 100644 index 0000000..e49ba6a --- /dev/null +++ b/inf/lige/1/3.txt @@ -0,0 +1,17 @@ +3 +6 +3 +3 +6 +7 +10 +10 +3 +500 +600 +700 +4 +50 +60 +70 +70 diff --git a/inf/lige/1/4.c b/inf/lige/1/4.c new file mode 100644 index 0000000..dfdf2a1 --- /dev/null +++ b/inf/lige/1/4.c @@ -0,0 +1,94 @@ +#include +#include +#include +struct cesta { + int w; + int x; + int y; +}; +int primerjaj_ceste (const void * a, const void * b) { + const struct cesta * c = (const struct cesta *) a; + const struct cesta * d = (const struct cesta *) b; + return c->w - d->w; +} +void obisci (char * adj, int n, int x, char * obiskal) { + obiskal[x] = 1; + char * off = adj + x*n; + for (int i = 0; i < n; i++) + if (off[i] && !obiskal[i]) + obisci(adj, n, i, obiskal); +} +int povezan (char * adj, int n) { + char * obiskal = calloc(n, sizeof *obiskal); + obisci(adj, n, 0, obiskal); + for (int i = 0; i < n; i++) + if (!obiskal[i]) { + free(obiskal); + return 0; + } + free(obiskal); + return 1; +} +int main (void) { + char buf[128]; + fgets(buf, 128, stdin); + char * c = buf; + int n = strtol(c, &c, 10); + c++; + int m = strtol(c, &c, 10); + int i = m; + struct cesta * ceste = calloc(m, sizeof *ceste); + int skupen_w = 0; + char * adj = calloc(n*n, sizeof *adj); + while (i--) { + fgets(buf, 128, stdin); + c = buf; + ceste[i].x = strtol(c, &c, 10)-1; + ceste[i].y = strtol(++c, &c, 10)-1; + skupen_w += ceste[i].w = strtol(++c, &c, 10); + adj[n*ceste[i].x+ceste[i].y]++; + adj[n*ceste[i].y+ceste[i].x]++; + } + qsort(ceste, m, sizeof(struct cesta), primerjaj_ceste); +#ifdef xxx + for (int i = 0; i < m; i++) + printf("w: %d\tpovezava: %d\t%d\n", ceste[i].w, ceste[i].x, ceste[i].y); +#endif + int od_w = 0; + /* + if (!povezan(adj, n)) { + fprintf(stderr, "NI POVEZAN!\n"); + for (int i = 0; i < n*n; i++) { + fprintf(stderr, "%d ", adj[i]); + if (!((i+1)%n)) + fprintf(stderr, "\n"); + } + } + */ + for (int i = m-1; i >= 0; i--) { + adj[n*ceste[i].x+ceste[i].y] = 0; + adj[n*ceste[i].y+ceste[i].x] = 0; + if (!povezan(adj, n)) { + adj[n*ceste[i].x+ceste[i].y]++; + adj[n*ceste[i].y+ceste[i].x]++; + } else { + od_w += ceste[i].w; + } + } + /* + fprintf(stderr, "skupen_w: %d\n", skupen_w); + for (int i = 0; i < m; i++) { + if (adj[n*ceste[i].x + ceste[i].y] == 0) { + fprintf(stderr, "x\n"); + izbran_w += ceste[i].w; + adj[n*ceste[i].x + ceste[i].y]++; + adj[n*ceste[i].y + ceste[i].x]++; + } + if (povezan(adj, n)) { + fprintf(stderr, "POVEZAN!\n"); + } else if (i == m-1) + fprintf(stderr, "NAPAKA!\n"); + } + */ + printf("%d\n", od_w); +} diff --git a/inf/lige/1/4.txt b/inf/lige/1/4.txt new file mode 100644 index 0000000..287df12 --- /dev/null +++ b/inf/lige/1/4.txt @@ -0,0 +1,7 @@ +5 6 +1 2 4 +5 3 10 +1 3 5 +2 4 2 +4 5 15 +3 4 7 -- cgit v1.2.3