Давайте разберём решение сложной, но очень интересной задачи. Сначала внимательно читаем условие:
Пункт про вывод -1 при отсутствии антиарифметической перестановки может сбить с толку и навести на мысль, что они лишь небольшого размера. И интуитивно так и может показаться, ведь добавление каждого последующего числа уменьшает варианты для продолжения.
Однако, это неверно. И антиарифметическая перестановка существует для любого N. И чем больше N, тем их больше (в абсолютном выражении, но не в относительном к общему числу перестановок). Например, на сайте, где собраны всевозможные последовательности, можно найти последовательность из количества таких перестановок: A003407. Например для N = 32 существует больше 121 миллиарда антиарифметических перестановок.
Как же построить хотя бы одну такую перестановку? Давайте попробуем по индукции. Пусть имеется две антиарифметические перестановки
A = (a1, a2, ..., am) и B = (b1, b2, ..., bm).
Тогда перестановка
(2 * a1, 2 * a2, ..., 2 * am, 2 * b1 + 1, 2 * b2 + 1, ..., 2 * bm + 1)
будет антиарифметической. То есть первую половину сделаем из чётных чисел, а вторую - из нечётных. Давайте докажем, что полученная перестановка будет арифметической, методом от противного. Пусть существует тройка чисел, которая образует арифметическую прогрессию, тогда возможны всего два варианта:
(2 * ai, 2 * aj, 2 * bk + 1) и (2 * ai, 2 * bj + 1, 2 * bk + 1).
Но в обоих случаях разница между элементами будет отличаться (даже чётностью). Таким образом мы получили противоречие.
Из этого доказательства мы сразу можем получить решение задачи: надо начать с перестановки из одного нуля и последовательно удваивать её длину.
Считаем входное число и инициализируем перестановку:
Так как заранее неизвестно, сколько будет итераций, будем использовать цикл while, пока длина списка будет меньше N. А на каждой итерации будем склеивать две версии списка с прошлой итерации:
Осталось вывести ответ, но в списке могут быть значения не меньше N, так как список каждый раз удваивается. Поэтому надо отфильтровать все неподходящие значения:
Люблю задачи, в которых можно применить аппарат строгого доказательства. А вы?
Предыдущий выпуск: Задача 272. Сумма максимума и минимума
Я очень хочу, чтобы мои советы были полезны вам, а для того, чтобы быстрее всех получать новые статьи можно подписаться на мой канал.
