1 files changed, 96 insertions, 0 deletions
diff --git a/inf/zotksd/4.c b/inf/zotksd/4.c
new file mode 100644
index 0000000..4c3113a
--- /dev/null
+++ b/inf/zotksd/4.c
@@ -0,0 +1,96 @@
+// todo: pazi na težave s prvim elementom
+#include <stdio.h>
+#include <stdlib.h>
+#include <limits.h>
+#define S 1600002
+#define ABS(x) ((x) > 0 ? (x) : -(x))
+int main (void) {
+	int ukazov = 0;
+	char buf[S];
+	fgets(buf, S, stdin);
+	int n = strtol(buf, NULL, 10);
+	fgets(buf, S, stdin);
+	char * cp = buf;
+	int * arr = calloc(n, sizeof *arr);
+	int * repr = calloc(10e6, sizeof *arr);
+	int najrepr = 0;
+	int najreprval = 0;
+	for (int i = 0; i < n; i++) {
+		arr[i] = strtol(cp, &cp, 10);
+		if (++repr[arr[i]] > najreprval) {
+			najreprval = repr[arr[i]];
+			najrepr = arr[i];
+		}
+		cp++;
+	}
+	free(repr);
+	int razd_od_centr = INT_MAX;
+	int center = 0;
+	if (najreprval == 1) {
+		najrepr = arr[n/2];
+		center = n/2;
+	}
+	for (int i = 0; i < n; i++) {
+		if (arr[i] == najrepr && ABS(n/2-i) < razd_od_centr) {
+			razd_od_centr = ABS(n/2-i);
+			center = i;
+		}
+	}
+	if (najreprval == 1) {
+		center = n/2;
+	}
+#ifndef EVAL
+	fprintf(stderr, "najrepr je število %d, ki ima toliko pojavitev: %d\n", najrepr, najreprval);
+#endif
+	int levo = 0;
+	int desno = n-1;
+	s:
+	while (arr[levo] == najrepr) {
+		if (levo == n-1)
+			goto k;
+		levo++;
+	}
+	while (arr[desno] == najrepr) {
+		if (desno == 0)
+			goto k;
+		desno--;
+	}
+	if (levo == desno) {
+		ukazov++;
+		goto k;
+	}
+	if (center > levo && center < desno) {
+		ukazov++;
+		arr[levo] = najrepr;
+		arr[desno] = najrepr;
+#ifndef EVAL
+		fprintf(stderr, "(%d, %d, %d) .. cached center\n", levo, center, desno);
+#endif
+		goto s;
+	}
+	center = 0;
+	for (int i = levo+1; i < desno; i++) {
+		if (arr[i] == najrepr) {
+			center = i;
+			arr[levo] = najrepr;
+			arr[desno] = najrepr;
+			ukazov++;
+#ifndef EVAL
+			fprintf(stderr, "(%d, %d, %d) .. našel center, en ukaz\n", levo, center, desno);
+#endif
+			goto s;
+		}
+	}
+	if (center == 0) {
+		ukazov += 2;
+		arr[levo] = najrepr;
+		arr[desno] = najrepr;
+		arr[(center = levo+(desno-levo)/2)] = najrepr;
+#ifndef EVAL
+		fprintf(stderr, "(%d, %d, %d) .. ni bilo centra, dva ukaza\n", levo, center, desno);
+#endif
+		goto s;
+	}
+	k:
+	printf("%d\n", ukazov);
+}