Я уже разбирал одну задачу на перебор (Задача 71. Две кучки камней), но там был перебор подмножеств, сейчас хочу показать, как можно легко перебирать расположение.
Перестановки - это классический пример расположения элементов друг относительно друга. Если не наложено никаких ограничений, то существует n! = 1 * 2 * ... * n (факториал) различных перестановок длины n. Действительно, первый элемент можно поставить одним способом, второй можно поставить слева или справа от него (два варианта), у третьего элемента уже три окна возможностей, и так далее. Каждый выбор независим, поэтому общее количество равно произведению.
В этой задаче на перестановки накладываются ограничения, поэтому не все они будут им соответствовать (кроме случая, когда k >= n - 1), и у нас не получится посчитать ответ по формуле. Но можно попробовать перебрать все перестановки.
Здесь размер перестановок не превышает 9, то есть максимальное количество, которое потребуется перебрать, равно 9! = 362880. Это вполне себе небольшое число, если учесть, что на С++ за секунду выполняется примерно 300 миллионов операций.
Для перебора перестановок воспользуемся функцией из стандартной библиотеки шаблонов next_permutation (по аналогии есть prev_permutation), которая находится в algorithm. Эта функция находит следующую в лексикографическом порядке перестановку. Например из перестановки 1 3 5 4 2 получается перестановка 1 4 2 3 5. Если же на вход передали последнюю перестановку (то есть вида n n-1 n-2 ... 2 1), то функция сделает из неё первую, но вернёт false.
Начнём с подключения библиотек:
Математическая библиотека понадобится для вычисления модуля числа, когда будем проверять отличаются ли числа меньше чем на k или нет, потому что для этого достаточно проверить модуль разности между данными числами.
Считываем данные, их немного:
После этого надо подготовить перестановку для перебора. Так как наша функция будет каждый раз находить следующую перестановку, то, для перебора всех перестановок, надо начинать с первой (в которой числа расположены по неубыванию):
Я сделал перестановку из n чисел, начиная с 0, а не с 1, как это принято в математике и описано в задаче. Просто потому что это никак не влияет на ответ и работу программы. Функции next_permutation можно передавать любой вектор из любых элементов (для которых есть операции сравнения), а не перестановки с строгом смысле. Да и на разность между соседними элементами это не влияет, если все они будут на 1 меньше.
Перебирать перестановки удобно с помощью цикла do...while. На каждой итерации внутри цикла получается новая перестановка, и мы можем выполнить с ней все необходимые операции (в нашем случае - проверить её на соответствие условию). А когда цикл дойдёт до последней, то функция next_permutation вернёт false, и произойдёт выход из цикла.
Проверку условия делаем простым проходом по всех элементам вектора (начиная со второго) и сравниваем их с предыдущим. В логической переменной f изначально лежит true, но если хотя бы для одной пары соседних элементов условие не выполнится, то f станет false и больше не будет меняться.
А в переменной res считаем количество подошедших перестановок. Если f равно true, то прибавляется 1, иначе 0. Осталось вывести ответ:
Такой простой способ перебрать позиции. Эту же задачу можно решать и с помощью рекурсии. При данных условиях в этом нет необходимости. Но если бы длина перестановок была больше, а ограничения на них сильнее (например n до 15, а k до 5), то при постепенном построении перестановки в рекурсии получили бы выигрыш в скорости.
Предыдущий выпуск: Задача 638. Всероссийская олимпиада по информатике
Я очень хочу, чтобы мои советы были полезны вам, а для того, чтобы быстрее всех получать новые статьи можно подписаться на мой канал.
