1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
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));
}
|
