Untitled

2
mail@pastecode.io avatar
unknown
plain_text
2 months ago
1.0 kB
3
Indexable
Never
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

int ans = 0;

void swap(int* a, int* b) {
    int temp = *a;
    *a = *b;
    *b = temp;
}

bool is_beautiful(int* perm, int n, int k) {
    int count = 0;
    for (int i = 0; i < n - 1; i++) {
        if (perm[i] > perm[i + 1]) {
            count++;
        }
    }
    return count <= k;
}

void getperms(int* perm, int start, int n, int k) {
    if (start == n) {
        if (is_beautiful(perm, n, k)) {
            ans++;
        }
    } else {
        for (int i = start; i < n; i++) {
            swap(&perm[start], &perm[i]);
            getperms(perm, start + 1, n, k);
            swap(&perm[start], &perm[i]);
        }
    }
}

int main() {
    int n, k;
    scanf("%d %d", &n, &k);

    int* perm = (int*)malloc(sizeof(int) * n);
    for (int i = 0; i < n; i++) {
        perm[i] = i + 1;
    }

    getperms(perm, 0, n, k);
    printf("%d\n", ans);

    free(perm);
    return 0;
}
Leave a Comment