Решение задачи "K-перестановки" с Acmp

С пояснением   Просмотров: 33


Назовем перестановку из N чисел 1…N K-перестановкой, если любые два соседних в ней элемента отличаются не более, чем на K.

Требуется найти число K-перестановок из N чисел от 1 до N.

Код

#include <bits/stdc++.h>

using namespace std;

int main()
{
    int n, k, res = 0;
    cin >> n >> k;
    string s = "";
    for(int i = 1; i <= n; ++i)
        s += i + 48;
    bool b = true;
    for(int i = 0; i < s.size() - 1; ++i){
        int t1 = s[i] - 48;
        int t2 = s[i + 1] - 48;
        if(abs(t1 - t2) > k)
            b = false;
    }
    if(b)
        ++res;
    while(next_permutation(s.begin(), s.end())){
        b = true;
        for(int i = 0; i < s.size() - 1; ++i){
            int t1 = s[i] - 48;
            int t2 = s[i + 1] - 48;
            if(abs(t1 - t2) > k)
                b = false;
        }
        if(b)
            ++res;
    }
    cout << res;
    return 0;
}

         

 Администратор Photo Автор: Администратор


Решение перебором. Советую погуглить функцию next_permutation() тем кто не знает.

Отправить решение задачи
Чтобы отправить решение вам нужно войти в систему или зарегистрироваться

Комментарии

Чтобы написать комментарии вам нужно войти в систему или зарегистрироваться