Скайлайн#12306

Скайлайн (Розбір)

Автор проблеми:	Хасан Салех (MathModel)
Підготовлено:	Хасан Салех (MathModel)
Редагував:	Хасан Салех (MathModel)

Розв'язок

Нам дана перестановка $p$ з ${1, 2, \dots, n}$ \{1,2,\dots,n\} і визначаємо

a_{i} = \frac{p _{i}}{i} .

a_i=\frac{p_i}{i}.

Необхідна умова:

a_{1} < a_{2} > a_{3} < a_{4} > a_{5} < \dots

a_1<a_2>a_3<a_4>a_5<\dots

тобто парні індекси є локальними максимумами, а непарні індекси є локальними мінімумами.

Замість того, щоб безпосередньо порівнювати сусідів, ми накладаємо більш сильний інваріант:

для кожного парного індексу $i$ , зробіть
$a_{i} > 1,$
a_i>1,
для кожного непарного індексу $i \geq 3$ i\ge3, зробіть
$a_{i} < 1.$
a_i<1.

Якщо це виконується, умова зигзагу автоматично задовольняється.

Отже, нам потрібна лише перестановка, яка забезпечує ці нерівності.

Конструкція

встановіть
$p_{1} = 1,$
p_1=1,
тоді
$a_{1} = 1.$
a_1=1.
для кожного парного індексу $i < n$ i<n, встановіть
$p_{i} = i + 1, a_{i} = \frac{i + 1}{i} > 1.$
p_i=i+1, \qquad a_i=\frac{i+1}{i}>1.
для кожного непарного індексу $i \geq 3$ i\ge3, встановіть
$p_{i} = i - 1, a_{i} = \frac{i - 1}{i} < 1.$
p_i=i-1, \qquad a_i=\frac{i-1}{i}<1.
якщо $n$ парне, встановіть
$p_{n} = n, a_{n} = 1.$
p_n=n, \qquad a_n=1.

Це безпосередньо дає

p = [1, 3, 2, 5, 4, 7, 6, \dots]

p=[1,\,3,\,2,\,5,\,4,\,7,\,6,\,\dots]

(з $n$ в кінці, якщо $n$ парне).

Дійсна конструкція існує для всіх $n \geq 1$ n\ge1, тому ми ніколи не виводимо $- 1$ .

Складність $O (n)$ .

for _ in range(int(input())):
    n=int(input())
    p=[0]*n
    for i in range(n):p[i]=i+1
    for i in range(1,n-1,2):
        p[i],p[i+1]=p[i+1],p[i]
    a=[p[i]/(i+1) for i in range(n)]
    for i in range(1,n-1):
        if(i%2==0):
            assert(a[i-1]>a[i] and a[i]<a[i+1])
        else:
            assert(a[i-1]<a[i] and a[i]>a[i+1])
    print(*p)

Python