summaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
-rw-r--r--.gitignore1
-rw-r--r--inf/lige/1/.gitignore1
-rw-r--r--inf/lige/1/1.c50
-rw-r--r--inf/lige/1/1.txt6
-rw-r--r--inf/lige/1/2.c70
-rw-r--r--inf/lige/1/2.txt5
-rw-r--r--inf/lige/1/3.c52
-rw-r--r--inf/lige/1/3.txt17
-rw-r--r--inf/lige/1/4.c94
-rw-r--r--inf/lige/1/4.txt7
10 files changed, 303 insertions, 0 deletions
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 <stdio.h>
+#include <stdlib.h>
+#include <string.h>
+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 <stdio.h>
+#include <string.h>
+#include <stdlib.h>
+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 <stdio.h>
+#include <stdlib.h>
+#include <math.h>
+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 <stdio.h>
+#include <stdlib.h>
+#include <string.h>
+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