6 files changed, 125 insertions, 0 deletions
diff --git a/šola/aps1/dn/osvetlitev/Makefile b/šola/aps1/dn/osvetlitev/Makefile
new file mode 100644
index 0000000..2d78386
--- /dev/null
+++ b/šola/aps1/dn/osvetlitev/Makefile
@@ -0,0 +1,4 @@
+program: resitev.cpp
+	g++ -Wall -Wextra -pedantic -Wformat-security -std=c++20 -o$@ $<
+clean:
+	rm program
diff --git a/šola/aps1/dn/osvetlitev/in.txt b/šola/aps1/dn/osvetlitev/in.txt
new file mode 100644
index 0000000..76b90fe
--- /dev/null
+++ b/šola/aps1/dn/osvetlitev/in.txt
@@ -0,0 +1,9 @@
+30
+7
+10 2
+23 2
+14 1
+4 1
+14 4
+11 5
+1 2
diff --git a/šola/aps1/dn/osvetlitev/resitev.cpp b/šola/aps1/dn/osvetlitev/resitev.cpp
new file mode 100644
index 0000000..0a17f31
--- /dev/null
+++ b/šola/aps1/dn/osvetlitev/resitev.cpp
@@ -0,0 +1,46 @@
+#include <stdio.h>
+#include <stdlib.h>
+#include <stdbool.h>
+struct event {
+	int pos;
+	bool tip; // true za začetek, false za konec
+};
+int compar_events (const void * a, const void * b) {
+	if (((struct event *) a)->pos == ((struct event *) b)->pos)
+		return 0;
+	if (((struct event *) a)->pos < ((struct event *) b)->pos)
+		return -1;
+	return 1;
+}
+int main (void) {
+	struct event events[20000];
+	int M, N, x, d;
+	scanf("%d %d", &M, &N);
+	for (int i = 0; i < N; i++) {
+		scanf("%d %d", &x, &d);
+		events[2*i].pos = x-d >= 0 ? x-d : 0;
+		events[2*i].tip = true;
+		events[2*i+1].pos = x+d <= M ? x+d : M;
+		events[2*i+1].tip = false;
+	}
+	qsort(events, 2*N, sizeof events[0], compar_events);
+	int osv = 0;
+	int depth = 0;
+	int start;
+	for (int i = 0; i < 2*N; i++) {
+		// fprintf(stderr, "pos=%d\ttip=%d\n", events[i].pos, events[i].tip);
+		if (events[i].tip == true) {
+			if (depth == 0)
+				start = events[i].pos;
+			depth++;
+		}
+		if (events[i].tip == false) {
+			depth--;
+			if (depth == 0)
+				osv += events[i].pos - start;
+		}
+	}
+	if (depth != 0)
+		fprintf(stderr, "depth == %d\n", depth);
+	printf("%d\n", M-osv);
+}
diff --git a/šola/aps1/dn/zlivanje/in.txt b/šola/aps1/dn/zlivanje/in.txt
new file mode 100644
index 0000000..eaca3bf
--- /dev/null
+++ b/šola/aps1/dn/zlivanje/in.txt
@@ -0,0 +1,26 @@
+25 3 2
+13
+18
+7
+8
+17
+3
+16
+9
+10
+11
+11
+0
+2
+19
+14
+5
+6
+15
+4
+5
+12
+3
+18
+1
+3
diff --git a/šola/aps1/dn/zlivanje/out.txt b/šola/aps1/dn/zlivanje/out.txt
new file mode 100644
index 0000000..6def2f9
--- /dev/null
+++ b/šola/aps1/dn/zlivanje/out.txt
@@ -0,0 +1 @@
+0 2 3 3 4 5 5 6 7 8 9 10 11 11 12 13 14 15 16 17 18 18 19 1 3
diff --git a/šola/aps1/dn/zlivanje/resitev.cpp b/šola/aps1/dn/zlivanje/resitev.cpp
new file mode 100644
index 0000000..8926019
--- /dev/null
+++ b/šola/aps1/dn/zlivanje/resitev.cpp
@@ -0,0 +1,39 @@
+#include <sys/param.h>
+#include <stdio.h>
+#include <stdlib.h>
+#include <stdbool.h>
+int compar_long (const void * a, const void * b) {
+	if (*(long *)a < *(long *)b)
+		return -1;
+	return *(long *)a > *(long *) b;
+}
+int main (void) {
+	long N, K, A;
+	scanf("%ld %ld %ld", &N, &K, &A);
+	long * d = (long *) malloc(N*sizeof *d);
+	long čet = 0;
+	long lastidx = 0;
+	long long četkončno = 1;
+	for (long i = 0; i < A && četkončno <= 2000000; i++)	// pravzaprav četkončno := K**A,
+		četkončno *= K;		// toda C nima int potence
+	// fprintf(stderr, "aaaaaaaa %ld\n", četkončno);
+	for (long i = 0; i < N; i++) {
+		scanf("%ld", d+i);
+		if (i && d[i-1] > d[i])
+			if (++čet >= četkončno) {
+				qsort(d+lastidx, i-lastidx, sizeof d[0], compar_long);
+				čet = 0;
+				lastidx = i;
+			}
+	}
+	qsort(d+lastidx, N-lastidx, sizeof d[0], compar_long);
+	bool devica = true;
+	for (long i = 0; i < N; i++) {
+		if (devica)
+			devica = false;
+		else
+			printf(" ");
+		printf("%ld", d[i]);
+	}
+	printf("\n");
+}