summaryrefslogtreecommitdiffstats
path: root/šola/p2/dn/DN08a_63230317.c
diff options
context:
space:
mode:
authorAnton Luka Šijanec <anton@sijanec.eu>2024-05-05 23:09:51 +0200
committerAnton Luka Šijanec <anton@sijanec.eu>2024-05-05 23:09:51 +0200
commitcef3899ce0ddea322e77307c1b6627c4c6ab9b27 (patch)
tree5d78bc61b08ce1b57f07668121f5d231b8dcd697 /šola/p2/dn/DN08a_63230317.c
parentthat was weird (diff)
downloadr-cef3899ce0ddea322e77307c1b6627c4c6ab9b27.tar
r-cef3899ce0ddea322e77307c1b6627c4c6ab9b27.tar.gz
r-cef3899ce0ddea322e77307c1b6627c4c6ab9b27.tar.bz2
r-cef3899ce0ddea322e77307c1b6627c4c6ab9b27.tar.lz
r-cef3899ce0ddea322e77307c1b6627c4c6ab9b27.tar.xz
r-cef3899ce0ddea322e77307c1b6627c4c6ab9b27.tar.zst
r-cef3899ce0ddea322e77307c1b6627c4c6ab9b27.zip
Diffstat (limited to 'šola/p2/dn/DN08a_63230317.c')
-rw-r--r--šola/p2/dn/DN08a_63230317.c106
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));
+}