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