diff options
author | Anton Luka Šijanec <anton@sijanec.eu> | 2024-05-05 23:09:51 +0200 |
---|---|---|
committer | Anton Luka Šijanec <anton@sijanec.eu> | 2024-05-05 23:09:51 +0200 |
commit | cef3899ce0ddea322e77307c1b6627c4c6ab9b27 (patch) | |
tree | 5d78bc61b08ce1b57f07668121f5d231b8dcd697 /šola/p2/dn/DN08a_63230317.c | |
parent | that was weird (diff) | |
download | r-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.c | 106 |
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)); +} |