13 files changed, 353 insertions, 0 deletions
diff --git a/inf/rtk/2021-šolsko-delo/dos/1.c b/inf/rtk/2021-šolsko-delo/dos/1.c
new file mode 100644
index 0000000..42b8402
--- /dev/null
+++ b/inf/rtk/2021-šolsko-delo/dos/1.c
@@ -0,0 +1,35 @@
+#include <stdio.h>
+
+int Izenaceno (char * s) { /* 0 ce ni izenaceno, 1, ce je izenaceno */
+	int c = 0; /* pozicija na nizu */
+	int k = 0; /* razlika med stevilom xov */
+	while (s[c] != '\0') { /* hodimo po nizu O(n) */
+		switch (s[c]) { /* pregledamo znak */
+			case 'x':
+				k++; /* povecamo relativno stevilo xov */
+				break;
+			case 'o':
+				k--; /* zmanjsamo relativno stevilo xov */
+				break;
+			default: /* ni niti o niti x */
+				return 0;
+		}
+		if (c >= 2 /* ce sta vsaj dva znakam, da preprecimo segmentation violation */
+				&& s[c] == s[c-1] && s[c] == s[c-2]) /* ce so trije po vrsti enaki */
+			return 0;
+		c++;
+	}
+	if (k != 0) /* ce xov ni enako kot ojev */
+			return 0;
+	return 1;
+}
+#if __INCLUDE_LEVEL__ == 0 /* da je lahko podprogram uporabljen kot knjiznica */
+int main (int argc, char ** argv) {
+	if (argc != 1+1) {
+		fprintf(stderr, "uporaba: %s niz\n", argv[0]); /* potrebujemo vhodni niz */
+		return 1; /* napaka */
+	}
+	fprintf(stderr, "zaporedje %s izenaceno\n", Izenaceno(argv[1]) ? "je" : "ni"); /* posredujemo odgovor podprograma */
+	return 0;
+}
+#endif
diff --git a/inf/rtk/2021-šolsko-delo/dos/1.exe b/inf/rtk/2021-šolsko-delo/dos/1.exe
new file mode 100755
index 0000000..243e4c3
--- /dev/null
+++ b/inf/rtk/2021-šolsko-delo/dos/1.exe
diff --git a/inf/rtk/2021-šolsko-delo/dos/2.c b/inf/rtk/2021-šolsko-delo/dos/2.c
new file mode 100644
index 0000000..5555a99
--- /dev/null
+++ b/inf/rtk/2021-šolsko-delo/dos/2.c
@@ -0,0 +1,36 @@
+#include <stdio.h>
+#include <stdlib.h>
+
+int podprogram (int * t /* tabela s kovanci */, int l /* dolzina tabele */) {
+	int c = 0; /* oznacuje, kje v tabeli trenutno smo */
+	int s = 0; /* sestevek */
+	int a = -2; /* kateri kupcek smo pobrali nazadnje */
+	int i = 0; /* indeks pri iteraciji */
+	while (c < l) { /* za vsak kupcek */
+		if (c-a > 1 && t[c] >= t[c+1]) { /* poberemo le, ce prej nismo pobarli in ce je naslednji manjsi ali enak trenutnemu */
+			for (i = c; i > a + 1; i = i - 2) /* ce je nekaj kupckov vmes med prejsnjim pobranim in tem, so urejeni po velikosti, gremo vzvratno in poberemo vsakega drugega. tukaj se pobere tudi trenutni. */
+				s += t[i];
+			a = c;
+		}
+		c++;
+	}
+	return s; /* vrnemo seštevek */
+}
+
+#if __INCLUDE_LEVEL__ == 0
+int main (int argc, char ** argv) {
+	if (argc < 2) { /* ni bilo povedanih nobenih kupckov */
+		fprintf(stderr, "uporaba: %s 1 2 3 4 ...\n", argv[0]);
+		return 1; /* zapremo program */
+	}
+	int * t = malloc(sizeof(int)*argc); /* pripravimo prostor za tabelo s kupcki, en kupcek vec */
+	int i = 1; /* indeks pri iteracijah */
+	for (i = 1; i < argc; i++) /* pretvorimo vhodne kupcke iz nizov v cela stevila */
+		t[i-1] = atoi(argv[i]); /* in jih postavimo v tabelo */
+	t[i-1] = 0; /* potrebujemo en namisljen kupcek vec, ki nima smeti v vrednosti */
+	fprintf(stdout, "sestevek: %d\n", podprogram(t, argc-1)); /* pozenemo podprogram in natisnemo izhodni sestevek */
+	free(t); /* sprostimo spomin, kjer je bila tabela dinamično alocirana */
+	t = NULL; /* zgolj kot dobro prakso vsakic po sproscanju nastavimo pointer na null, da preprecimo double-free napake (free ne naredi nicesar na naslovu 0x00) */
+	return 0; /* z uspesnim statusom zapremo program */
+}
+#endif
diff --git a/inf/rtk/2021-šolsko-delo/dos/2.exe b/inf/rtk/2021-šolsko-delo/dos/2.exe
new file mode 100755
index 0000000..ceadc08
--- /dev/null
+++ b/inf/rtk/2021-šolsko-delo/dos/2.exe
diff --git a/inf/rtk/2021-šolsko-delo/dos/3.c b/inf/rtk/2021-šolsko-delo/dos/3.c
new file mode 100644
index 0000000..9a2b186
--- /dev/null
+++ b/inf/rtk/2021-šolsko-delo/dos/3.c
@@ -0,0 +1,86 @@
+#include <stdio.h>
+#include <stdlib.h>
+#include <limits.h> /* ce te knjiznice ni, definiraj INT_MAX */
+#define abs(e) ((e) < (0 - (e)) ? 0 - (e) : (e)) /* da ne potrebujemo matematicne knjiznice - da rocni link matematike -lm ni potreben, definiramo absolutno vrednost stevila v preprocesorju */
+#define pot(iks,ipsilon,x,y) (abs(iks-x)+abs(ipsilon-y)) /* definiramo podano enacbo za pot, zaradi lepe berljivosti kode in zaradi hitrejsega delovanja programa kot preprocesorsko definicijo */
+
+struct koord { /* definiramo strukturo para koordinat, kot je to v navodilu */
+	int x;
+	int y;
+};
+
+struct koord * podprogram (
+		struct koord * ss, /* seznam koordinat stalnih strank */
+		size_t sss, /* stevilo stalnih strank */
+		struct koord * mc, /* seznam koordinat moznih central */
+		size_t mcs /* stevilo moznih central	*/
+		) {
+	int i = 0; /* indeks pri iteracijah */
+	int j = 0; /* indeks pri gnezdenih iteracijah 1. globine */
+	int s = 0; /* sestevek poti za trenutno pot */
+	int os = INT_MAX; /* stari sestevek */
+	struct koord * o; /* kazalec na trenutno najboljso centralo */
+	for (i = 0; i < mcs; i++) { /* za vsako mozno centralo */
+		s = 0; /* resetiramo sestevek poti */
+		for (j = 0; j < sss; j++) /* za vsako stalno stranko */
+			s += pot(mc[i].x, mc[i].y, ss[j].x, ss[j].y); /* povecamo sestevek poti */
+		if (s < os) { /* ce smo nasli novo najboljso pot - beri: najkrajso */
+			os = s; /* nastavimo staro pot na trenutno */
+			o = &mc[i]; /* nastavimo kazalec na odgovor na trenutno centralo */
+		}
+	}
+	return o; /* vrnemo kazalec z najbolj primerno centralo */
+}
+
+/* vhodni podatki v standardni vhod - na prvi vrstici so stalne stranke, na drugi pa mozne centrale. koncaj z EOF.
+ * 1,2 1,3 1,4 6,2 8,3 1,6 2,6 1,6
+ * 6,2 7,2 5,2 6,1
+ * */
+#if __INCLUDE_LEVEL__ == 0
+int main (int argc, char ** argv) {
+	struct koord * k = malloc(sizeof(struct koord)*1); /* inicializiramo spomin */
+	char * b = malloc(sizeof(char)*1); /* za hitrost ves vhod programa najprej shranimo v delovni spomin, inicializiramo odlagalisce za to */
+	size_t d = 0; /* dolzina stalnih strank */
+	size_t z = 0; /* zapisanih bajtov in kasneje dolzina moznih central */
+	char * p; /* kazalec za strtol */
+	struct koord * o; /* odgovor podprograma */
+	char c = fgetc(stdin); /* zacasni znak za branje v spomin iz standardnega vhoda */
+	while (!feof(stdin)) { /* dokler jedro operacijskega sistema ne nastavi zastavice z napako, da je konec vhoda */
+		b = realloc(b, sizeof(char)*(z+2)); /* povecamo spomin. POMEMBNO: tega ne delaj tako, ce gre za pomembno stvar. ce zmanjka delovnega spomina, bo b NULL in starega spomina ne bomo mogli sprostiti, torej bo spominska luknja ali se huje; segmentation violation. ceprav, ce je spomina zmanjkalo, nas bo itak prej ali slej ubil OOM morilec - uff, kaksen spis :=) */
+		b[z++] = c; /* zapisemo znak */
+		c = fgetc(stdin); /* dobimo nov znak, ce smo na koncu bomo potem izsli iz while() */
+	}
+	if (b[z-1] == '\n') /* ce se vnos konca z EOL */
+		z--; /* damo EOL stran */
+	if (b[z-1] == '\r') /* ce je bil to inferioren operacijski sistem, bo EOL CRLF, zato pocistimo se to */
+		z--;
+	b[z] = '\0'; /* z null-terminatorjem koncamo C-niz */
+	z = 0; /* pripravimo z na ponovno uporabo */
+	p = b; /* nastavimo kazalec. ce bi ga na zacetku, ne bi bilo vec okej, ker bi realloc lahko spremenil lokacijo b. s tem sem se pravzaprav relativno dolgo zafrkaval */
+	do { /* delamo malo drugacen while(), tu se bo "condition" preveril na koncu */
+		k = realloc(k, sizeof(struct koord)*(z+d+2)); /* povecamo velikost spomina */
+		k[z+d].x = strtol(p, &p, 10); /* izluscimo naslednje celo stevilo iz niza */
+		p++; /* preskocimo locilo (vejico) */
+		k[z+d].y = strtol(p, &p, 10); /* izluščimo se y koordinato */
+		if (z > 0) /* ce pisemo stalne stranke */
+			z++; /* vecamo njihovo stevilo */
+		else /* ce pa pisemo mozne centrale */
+			d++; /* pa vecamo njihovo stevilo */
+		if (p[0] == '\r') /* spet moramo poskrbeti, da program dela na slabsih operacijskih sistemih - beri: windows */
+			p++; /* preskocimo CR */
+		if (p[0] == '\n') /* ce smo na koncu prve vrstice */
+			z++; /* zacnemo pisati mozne centrale */
+		p++; /* gremo na naslednji znak niza. */
+	} while (p[-1] != '\0'); /* dokler ne pridemo do konca niza */
+	o = podprogram(k,
+			d,
+			&(k[d]), /* lahko bi bilo tudi k+d ampak meni tako izgleda bolj pregledno */
+			z);
+	fprintf(stdout, "postavite centralo na {\"x\": %d, \"y\": %d}\n", o->x, o->y);
+	free(b); /* o sproscanju spomina sem ze pisal */
+	b = NULL; /* in prav tako o moji praksi */
+	free(k);
+	k = NULL;
+	return 0; /* predvidevamo, da bo program vedno delal (; hahaha */
+}
+#endif
diff --git a/inf/rtk/2021-šolsko-delo/dos/3.exe b/inf/rtk/2021-šolsko-delo/dos/3.exe
new file mode 100755
index 0000000..cd7fd73
--- /dev/null
+++ b/inf/rtk/2021-šolsko-delo/dos/3.exe
diff --git a/inf/rtk/2021-šolsko-delo/dos/3.in b/inf/rtk/2021-šolsko-delo/dos/3.in
new file mode 100644
index 0000000..4455e14
--- /dev/null
+++ b/inf/rtk/2021-šolsko-delo/dos/3.in
@@ -0,0 +1,2 @@
+7,5 5,6 4,1 1,2
+7,2 5,3 3,5
diff --git a/inf/rtk/2021-šolsko-delo/dos/4.c b/inf/rtk/2021-šolsko-delo/dos/4.c
new file mode 100644
index 0000000..9703707
--- /dev/null
+++ b/inf/rtk/2021-šolsko-delo/dos/4.c
@@ -0,0 +1,75 @@
+#include <stdio.h>
+#include <stdlib.h>
+
+/* tukaj si kar nekaj kode izposodimo iz prejsnje naloge, predvsem za branje iz standardnega vhoda, zato ne bom pisal komentarjev tam, kjer so ze v nalogi 3. */
+
+struct preusm {
+	int s; /* izvorni naslov */
+	int t; /* naslov, na katerega bomo preusmerjeni */
+	int o; /* 1, v kolikor smo ze obiskali to preusmeritev, 0 na zacetku */
+};
+
+int podprogram(
+		struct preusm * p, /* seznam preusmeritev */
+		int n, /* stevilo preusmeritev */
+		int z /* naslov, ki naj ga funkcija obravnava - rekurzija */
+		) { /* vrne nic, ce se zacikla, vrne koncni naslov, ko se le-ta najde */
+	int i = 0; /* iteracijski decek */
+	for (i = 0; i < n; i++) /* za vsako preusmeritev */
+		if (p[i].s == z) { /* ko najdemo nas naslov */
+			if (p[i].o == 1) /* ups, ocitno se zacikla, na tej preusmeritvi smo ze bili */
+				return 0; /* vrnemo s statusom, ki zaznamuje zaciklanost */
+			p[i].o = 1; /* za v prihodnje zaznamujemo, da smo na tej preusmeritvi ze bili */
+			return podprogram(p, n, p[i].t); /* rekurzivno naprej sledimo preusmeritvam */
+		}
+	return z; /* ocitno tega naslova ni v tabeli preusmeritev, to je koncni naslov */
+}
+
+/* vhodni podatki - seznam preusmeritev
+ * 1,2 1,3 1,4 6,2 8,3 1,6 2,6 1,6
+ * argv[1] - z (zacetni naslov) v desetiskem sistemu
+ *
+ * jaz osebno menim, da n ni potreben in je tu samo zato, da me zavede. zatorej program ne uporablja nja, glede na navodilo pa ga mora sprejeti, zato ga dajte v argv[2], vendar ne bo uporabljen.
+ * */
+int main (int argc, char ** argv) {
+	if (argc < 1+1) { /* ce ni podanega zacetnega naslova */
+		fprintf(stderr, "uporaba: %s z (stevilka) < 4.in (preusmeritve)\n", argv[0]);
+		return 1; /* napaka */
+	}
+	struct preusm * k = malloc(sizeof(struct preusm)*1);
+	char * b = malloc(sizeof(char)*1);
+	size_t d = 0;
+	char * p;
+	char c = fgetc(stdin);
+	int o;
+	int z;
+	while (!feof(stdin)) {
+		b = realloc(b, sizeof(char)*(d+2));
+		b[d++] = c;
+		c = fgetc(stdin);
+	}
+	if (b[d-1] == '\n')
+		d--;
+	if (b[d-1] == '\r')
+		d--;
+	b[d] = '\0';
+	d = 0;
+	p = b;
+	z = atoi(argv[1]); /* pridobimo zacetni naslov */
+	do {
+		k = realloc(k, sizeof(struct preusm)*(d+2));
+		k[d].o = 0;
+		k[d].s = strtol(p, &p, 10 /* mimogrede, ta desetica oznacuje desetiski sistem */);
+		p++;
+		k[d].t = strtol(p, &p, 10);
+		p++;
+		d++;
+	} while (p[-1] != '\0');
+	o = podprogram(k, d, z);
+	fprintf(stdout, "%s%c%d\n", o == 0 ? "preusmeritev se zacikla\n" : "preusmeritve se koncajo na naslovu", o == 0 ? '\0' : ' ', o); /* malo format string magije */
+	free(b);
+	b = NULL;
+	free(k);
+	k = NULL;
+	return 0;
+}
diff --git a/inf/rtk/2021-šolsko-delo/dos/4.exe b/inf/rtk/2021-šolsko-delo/dos/4.exe
new file mode 100755
index 0000000..6cb7c32
--- /dev/null
+++ b/inf/rtk/2021-šolsko-delo/dos/4.exe
diff --git a/inf/rtk/2021-šolsko-delo/dos/4.in b/inf/rtk/2021-šolsko-delo/dos/4.in
new file mode 100644
index 0000000..e109dcb
--- /dev/null
+++ b/inf/rtk/2021-šolsko-delo/dos/4.in
@@ -0,0 +1 @@
+7,69 1,2 2,420 3,5 5,6 6,7 420,3 69,4
diff --git a/inf/rtk/2021-šolsko-delo/dos/5.c b/inf/rtk/2021-šolsko-delo/dos/5.c
new file mode 100644
index 0000000..6c5d0d9
--- /dev/null
+++ b/inf/rtk/2021-šolsko-delo/dos/5.c
@@ -0,0 +1,86 @@
+#include <stdio.h>
+#include <stdlib.h>
+#include <string.h>
+
+struct niz {
+	int d; /* dolzina niza */
+	char * n; /* niz */
+};
+
+/* funkcija odvrne 0, ce sta niza enako dolga, -1, ce je prvi krajsi od drugega in 1, ce je prvi daljsi od drugega */
+int primerjaj_niza (const void * a, const void * b) {
+	const struct niz * sna = (const struct niz *) a; /* Cjeva carovnija vlivanja */
+	const struct niz * snb = (const struct niz *) b;
+	return (sna->d > snb->d) - (sna->d < snb->d); /* preprosto primerjanje dveh stevilk */
+}
+
+struct niz * podprogram (
+		struct niz * n, /* seznam nizov */
+		int nizov, /* stevilo nizov */
+		struct niz * p /* prejsnji niz za rekurzijo */
+		) {
+	int i = 0; /* iteracijski decek */
+	int j = 0; /* iteracijski decek, ki je potopljen v 1. globino vgnezdene zanke */
+	int o = 0; /* oddaljenost prvega niza, ki ima vecjo dolzino */
+	int s = 0; /* ali smo ze en znak izpustili */
+	int a = 1; /* niz je aplikatibilen */
+	struct niz * od = p; /* kazalec na odgovor, nastavljen na prejsnji niz, ce nizi te velikosti niso vec aplikatibilni */
+	struct niz * op; /* kazalec na prihodnji morebitni odgovor, seveda zgolj, ce je daljsi */
+	int zadnja_runda = 0; /* samoumevno */
+	for (o = 0; n[o].d == n[0].d; o++) /* za vsak niz najkrajse dolzine */
+		if (o+1 >= nizov) { /* ce smo pri koncu seznama nizov */
+			zadnja_runda = 1; /* pri koncu seznama nizov smo, to si zabelezimo */
+			o++; /* ker se pri break tretji stavek for zanke ne izvede na koncu */
+			break;
+		}
+	for (i = 0; i < o; i++) { /* podobno kot prejsnja zanka, le da jnam je sedaj o znan */
+		s = 0; /* ponastavimo */
+		a = 1; /* ponastavimo */
+		for (j = 0; j < p->d; j++) { /* za vsak znak prejsnjega niza */
+			if (p->n[j] != n[i].n[j+s]) /* ce se nas niz za en znak vec ne ujema s prejsnjim */
+				s++;
+			if (s > 1) { /* ce se je prejsen ce stavek ze zgodil, smo izpustili ze dva znaka, kar ni dovoljeno */
+				a = 0; /* ta niz ni aplikatibilen */
+				break;
+			}
+		}
+		if (a && zadnja_runda) /* ce smo pri koncu in smo nasli aplikatibien niz - super, vrnemo ga skozi rekurzicno verigo, to je niz, ki ga iscemo (;:! */
+			return &n[i]; /* ja, spet bi lahko uporabil n+i ampak se mi tole zdi lepše */
+		if (a) {
+			op = podprogram(n+o, nizov-o, &n[i]); /* poklicemo podprogram z mnozico nizov zgolj vecjih velikosti, kot ta velikost - zato potrebujemo o (: */
+			if (op != NULL && op->d > od->d) /* ce je odgovor boljsi od do sedaj znanega */
+				od = op; /* kazalec na starega prepisemo */
+		}
+	}
+	return od;
+}
+
+/* argv+1 je seznam nizov.
+ * */
+#if __INCLUDE_LEVEL__ == 0
+int main (int argc, char ** argv) {
+	if (argc < 1+1) {
+		fprintf(stderr, "uporaba: %s splatters splatter platter latter later late ate at a (nenujno po velikosti)\n", argv[0]);
+		return 1;
+	}
+	struct niz * n = malloc(sizeof(struct niz)*argc); /* prostor za nize */
+	size_t i = 0; /* iteracijski decek */
+	struct niz * o; /* odgovor */
+	struct niz p = { /* virtualen prejsnji niz, ki ga damo v rekurzicno funkcijo */
+		.d = 0,
+		.n = "",
+	}; /* zato, da ni treba delati dodatnega preizkusa, ce je funkcija podprogram pognana iz funkcije podprogram ali iz uporabnkove funkcije, recimo main */
+	for (i = 0; i < argc-1; i++) { /* pridobimo velikosti nizov */
+		n[i].d = strlen(argv[1+i]); /* predpomnimo dolzino niza */
+		n[i].n = argv[i+1]; /* zapisemo kazalec do konstantnega niza iz argv */
+	}
+	/* sedaj pa nize razvrstimo po velikosti s funkcijo iz STANDARDNE KNJIZNICE qsort */
+	qsort(n, argc-1, sizeof(struct niz), primerjaj_niza);
+	/* sedaj pa lahko zacnemo z nasim skriptom */
+	o = podprogram(n, argc-1, &p);
+	fprintf(stdout, "%s\n", o->n);
+	free(n);
+	n = NULL;
+	return 0;
+}
+#endif
diff --git a/inf/rtk/2021-šolsko-delo/dos/5.exe b/inf/rtk/2021-šolsko-delo/dos/5.exe
new file mode 100755
index 0000000..07c24e6
--- /dev/null
+++ b/inf/rtk/2021-šolsko-delo/dos/5.exe
diff --git a/inf/rtk/2021-šolsko-delo/dos/berime.txt b/inf/rtk/2021-šolsko-delo/dos/berime.txt
new file mode 100644
index 0000000..98944d9
--- /dev/null
+++ b/inf/rtk/2021-šolsko-delo/dos/berime.txt
@@ -0,0 +1,32 @@
+naloge preverjeno delujejo v GNUC 11 na gnu/linux, ceprav bi morale delati
+normalno tudi na windows.
+
+vse naloge se prevede v strojni jezik z ukazom gcc %d.c, kjer je %d stevilka
+naloge (1-5). zunanje knjiznice, poleg standardne (glibc stdlib.h) in vhodno-izhodne
+(stdio.h), niso potrebne.
+
+izjema je tretja naloga, ki potrebuje limits.h, vendar lahko #include
+definicijo zamenjate z #define INT_MAX 4096, kjer je 4096 najvecje mozno celo
+stevilo (int podatkovni tip).
+
+se ena izjema je peta naloga, ki potrebuje string.h, vendar lahko #include
+definicijo zamenjate s svojo definicijo funkcije strlen.
+
+datoteke %d.in, kjer je %d stevilka naloge, so vhodne datoteke, kjer so
+podatki iz naloge. v program jih vstavite v stdin (./a.out < 3.in recimo)
+
+resitve bodo po koncu tekmovanja na
+https://git.šijanec.eu/sijanec/sola-gimb-2/src/branch/master/inf/rtk/2021-šolsko-delo
+
+prilozene so tudi binarne datoteke za linux z imeni %d.out, kjer je %d
+stevilka naloge od 1 do 5, prevedene z gcc -pedantic -Wall -g %d.c -o%d.out za
+procesorsko arhitekturo amd64.
+
+ce se vam koda ne prikaze lepo
+                              temvec so vrstice takole zamaknjene, odprite
+                                                                          c datoteke
+iz mape dos/, ki imajo windows koncnike vrstic (CRLF). programi podpirajo
+vhodne datoteke LF in CRLF.
+
+prilozene so tudi binarne datoteke za windows v mapi dos/, prevedene z ukazom
+x86_64-w64-mingw32-gcc-win32 -Wall -pedantic -g %d.c -o%d.exe.