2 files changed, 220 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));
+}
diff --git a/šola/p2/dn/DN08b_63230317.c b/šola/p2/dn/DN08b_63230317.c
new file mode 100644
index 0000000..e481d7c
--- /dev/null
+++ b/šola/p2/dn/DN08b_63230317.c
@@ -0,0 +1,114 @@
+#include <stdio.h>
+#include <stdlib.h>
+#include <stdbool.h>
+#include <string.h>
+/*
+bool kva (bool * črni, int n, int k, int * sklad, int globina) { // stara neuporabljena funkcija ... preskoči to
+	if (črni[n-1]) // memo recall
+		return true;
+	if (n <= k) {
+ 		for (int i = 0; i < globina; i++)
+			printf("%d -> [%d] -> ", sklad[2*i], sklad[2*i+1]);
+		printf("%d\n", n);
+		return false;
+	}
+	bool črni_zmaga = true; // začnimo s tako predpostavko in jo ovržimo, čim najdemo kandidata za zmago belega
+	for (int i = 1; i < n && i <= k; i++) { // pobiranje belega
+		if (n-i <= k) // črni izprazni kup
+			break; // s takim ali večjim pobiranjem ne najdemo za belega ugodne rešitve
+		sklad[globina*2] = i;
+		bool beli_zmaga = true; // beli mora zmagati za vse možne odgovore črnega, da ...
+		for (int j = 1; j < n-i && j <= k; j++) { // možni odgovori črnega
+			sklad[globina*2+1] = j;
+			beli_zmaga &= !kva(črni, n-i-j, k, sklad, globina+1);
+		}
+		črni_zmaga &= !beli_zmaga; // ... lahko nastavimo črni_zmaga na false
+		sklad[globina] = i;
+	}
+	if (črni_zmaga) {
+		črni[n-1] = true; // memo sto
+		return true;
+	}
+	return false;
+}
+*/
+void zmage (int n, int k, bool dp[n+1], bool bele_poteze[n+1][k+1], int sklad[2*n], int globina) {
+	if (n <= k) {
+ 		for (int i = 0; i < globina; i++)
+			printf("%d -> [%d] -> ", sklad[2*i], sklad[2*i+1]);
+		printf("%d\n", n);
+		return;
+	}
+	/* if (!dp[n])
+		return; */
+	for (int i = 1; i <= k && i <= n; i++) { // iščemo zmagovito belo potezo
+		if (bele_poteze[n][i]) { // i je zmagovita bela poteza ob številu preostalih žetonov n
+			sklad[2*globina] = i;
+			for (int j = 1; j <= k && j <= n-i; j++) { // vsi črni odgovori vodijo v zmagovito belo stanje žetonov
+				sklad[2*globina+1] = j;
+				zmage(n-i-j, k, dp, bele_poteze, sklad, globina+1);
+			}
+		}
+	}
+	/* for (int i = 1; i <= k && i <= n; i++) { // bela poteza
+		if (dp[n-i]) { // je zmagovita
+			sklad[2*globina] = i;
+			for (int j = 1; j <= k && j <= n-i; j++) { // črni odgovor
+				sklad[2*globina+1] = j;
+				zmage(n-i-j, k, dp, bele_poteze, sklad, globina+1);
+			}
+		}
+	} */
+}
+int main (void) {
+	int n, k;
+	scanf("%d %d\n", &n, &k);
+	bool dp[n+1]; // true je beli, false je črni, beli je na potezi, indeks je preostalih žetonov, vrednost je zmagovalec
+	bool bele_poteze[n+1][k+1]; // prevelika 2d tabela za bele odgovore ob danem preostalem številu žetonov. druga dimenzija je bitfield. true, če beli zmaga, false, če črni, za dano potezo belega.
+	for (int i = 1; i <= n; i++) {
+		dp[i] = false;
+		for (int j = 1; j <= k && j <= i; j++) { // bela poteza
+			bool beli_zmaga = true;
+			if (i-j == 0)
+				beli_zmaga = true;
+			else
+				for (int l = 1; l <= k && l <= i-j; l++) // iščemo en črni odgovor
+					if (!dp[i-j-l]) { // a črni s tem odgovorom zmaga
+						beli_zmaga = false;
+						break;
+					}
+			if (beli_zmaga) {
+				dp[i] = true;
+				bele_poteze[i][j] = true;
+			} else
+				bele_poteze[i][j] = false;
+		}
+	}
+	fprintf(stderr, "   ");
+	for (int i = 0; i <= n; i++)
+		if (!(i % 10))
+			fprintf(stderr, "%d         ", i/10);
+	fprintf(stderr, "\n   ");
+	for (int i = 0; i <= n; i++)
+		fprintf(stderr, "%d", i%10);
+	fprintf(stderr, "\ndp: ");
+	for (int i = 1; i <= n; i++)
+		fprintf(stderr, "%s", dp[i] ? "@" : "_");
+	fprintf(stderr, "\t(@ je zmaga belega, _ je zmaga črnega)\n");
+	for (int i = 1; i <= n; i++) {
+		fprintf(stderr, "preostalo žetonov %d. poteze belega: ", i);
+		for (int j = 1; j <= k; j++) {
+			if (bele_poteze[i][j]) {
+				fprintf(stderr, "%d, ", j);
+			}
+		}
+		fprintf(stderr, "\n");
+	}
+	if (!dp[n]) {
+		printf("CRNI\n");
+		return 0;
+	}
+	int sklad[2*n];
+	memset(sklad, 0, sizeof sklad);
+	zmage(n, k, dp, bele_poteze, sklad, 0);
+}
\ No newline at end of file