summaryrefslogblamecommitdiffstats
path: root/šola/p2/dn/DN08a_63230317.c
blob: 860c42271e5d30ba427e725c2eac450c40421292 (plain) (tree)









































































































                                                                                                  
#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));
}