1 files changed, 106 insertions, 0 deletions

diff --git a/šola/p2/dn/DN08a_63230317.c b/šola/p2/dn/DN08a_63230317.c
new file mode 100644
index 0000000..860c422
--- /dev/null
+++ b/šola/p2/dn/DN08a_63230317.c
@@ -0,0 +1,106 @@
+#include <stdio.h>
+#include <stdlib.h>
+// #include <search.h>
+#include <stdbool.h>
+#include <assert.h>
+#include <string.h>
+void swap (int * seq, int i, int j, int r) {
+	while (r--) {
+		int bckp = seq[i+r];
+		seq[i+r] = seq[j+r];
+		seq[j+r] = bckp;
+	}
+}
+/*
+#define N 10
+struct seq {
+	int elem[N];
+	int count;
+};
+int compar (const void * a, const void * b) {
+	for (int i = 0; i < N; i++)
+		if (((struct seq *) a)->elem[i] != ((struct seq *) b)->elem[i])
+			return ((struct seq *) a)->elem[i] > ((struct seq *) b)->elem[i] ? 1 : -1;
+	return 0;
+}
+void insert (void ** root, struct seq * seq, int n, int r, int remain) {
+	for (int i = 0; i+2*r <= n; i++)
+		for (int j = i+r; j+i <= n; j++) {
+			struct seq * seq2 = calloc(1, sizeof *seq2);
+			memcpy(seq2, seq, sizeof *seq2);
+			swap(seq2->elem, i, j, r);
+			struct seq ** ret = tsearch(seq2, root, compar);
+			if (seq2 == *ret) {
+				free(seq2);
+				seq2 = *ret;
+			}
+			seq2->count++;
+			if (remain-1)
+				insert(root, seq, n, r, remain-1);
+		}
+}
+int count (void ** root, struct seq * seq, int n, int r, int remain) {
+	int število = 0;
+	for (int i = 0; i+2*r <= n; i++)
+		for (int j = i+r; j+i <= n; j++) {
+			swap(seq->elem, i, j, r);
+			struct seq ** ret = tfind(seq, root, compar);
+			if (ret)
+				število += (*ret)->count;
+			if (remain-1)
+				count(root, seq, n, r, remain-1);
+			swap(seq->elem, i, j, r);
+		}
+	return število;
+}
+int intcompar (const void * a, const void * b) {
+	if (*((int *)a) == *((int *)b))
+		return 0;
+	return *((int *) a) < *((int *) b) ? -1 : 1;
+}
+*/
+bool sorted (int * seq, int n) {
+	bool up = true;
+	bool down = true;
+	while (--n) {
+		if (seq[n] < seq[n-1])
+			up = false;
+		if (seq[n] > seq[n-1])
+			down = false;
+	}
+	return up;
+}
+int count (int * seq, int n, int r, int remain) {
+	int število = 0;
+	for (int i = 0; i+2*r <= n; i++)
+		for (int j = i+r; j+r <= n; j++) {
+			swap(seq, i, j, r);
+			if (sorted(seq, n))
+				število++;
+			if (remain-1)
+				število += count(seq, n, r, remain-1);
+			swap(seq, i, j, r);
+		}
+	return število;
+}
+int main (void) {
+	int n, k, r;
+	scanf("%d %d %d\n", &n, &k, &r);
+	/* struct seq seq;
+	memset(&seq, 0, sizeof seq);
+	for (int i = 0; i < n; i++)
+		scanf("%d", &seq.elem[i]);
+	void * root = NULL;
+	tsearch(&seq, &root, compar);
+	insert(&root, &seq, n, r, k/2);
+	qsort(seq.elem, n, sizeof seq.elem[0], intcompar); */
+	/* int seqdebug[10] = {14, 12, 19, 16, 18, 11, 15, 10, 13, 17};
+	swap(seqdebug, 0, 3, 3);
+	swap(seqdebug, 2, 5, 3);
+	swap(seqdebug, 0, 4, 3);
+	swap(seqdebug, 2, 7, 3); */
+	int seq[n];
+	for (int i = 0; i < n; i++)
+		scanf("%d", &seq[i]);
+	printf("%d\n", count(seq, n, r, k) + sorted(seq, n));
+}