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.