Перестановкой длины n называется последовательность из n чисел, в которой каждое из чисел от

1 до n встречается ровно 1 раз. Например, (3, 4, 5, 1, 2) и (1, 2) - перестановки, а (1, 4, 3) и (2, 1, 3, 2)

- нет.

Назовем перестановку хитрой, если для любых двух соседних чисел в перестановке разница

между ними больше или равна минимальному из них. Например, перестановка

(3, 1, 2, 4)

является хитрой, поскольку |3 - 1| ⩾ min (3, 1), |1 - 2| ⩾ min (1, 2) и |2 - 4| ⩾ min (2, 4).

Дано число n, найдите хитрую перестановку длины n.

Question

Информатика

Азелла

25 ноября, 13:16

Перестановкой длины n называется последовательность из n чисел, в которой каждое из чисел от

1 до n встречается ровно 1 раз. Например, (3, 4, 5, 1, 2) и (1, 2) - перестановки, а (1, 4, 3) и (2, 1, 3, 2)

- нет.

Назовем перестановку хитрой, если для любых двух соседних чисел в перестановке разница

между ними больше или равна минимальному из них. Например, перестановка

(3, 1, 2, 4)

является хитрой, поскольку |3 - 1| ⩾ min (3, 1), |1 - 2| ⩾ min (1, 2) и |2 - 4| ⩾ min (2, 4).

Дано число n, найдите хитрую перестановку длины n.

+3

Ответы (1)

Знаете ответ на вопрос?

Дениса · Answer 1

Легко видеть, что перестановка вида (N, N - 2, N - 4, ..., 2, 1, 3, 5, 7, ..., N - 1) для четного N и (N - 1, N - 3, N - 5, ..., 2, 1, 3, 5, 7, ..., N) для нечетного N - хитрые (в каждой перестановке сначала выписаны все четные числа в обратном порядке, а потом все нечётные в обычном).

Код на питоне, генерирующий такую перестановку:

N = int (input ())

print (* ([x for x in range ((N//2) * 2, 0, - 2) ]+[x for x in range (1, N, 2) ]))