Профессор перед экзаменом попросил ассистента подготовить список номеров вопросов для каждого студента. Так как профессор планирует подробно спрашивать материал курса, то каждый…

Решение задачки по принципу максимального минимального расстояния на одной прямой.

Идея:

• Пусть старый список имеет позиции 0..N-1. Первый номер в новом списке должен быть тем же, что на позиции 0: A[0].
• Чтобы выбрать следующий номер, нужно максимизировать минимальное расстояние до уже выбранных позиций в старом списке. После выбора 0 и N-1 остаётся единственный сегмент [0, N-1] между двумя крайними выбранными точками. Следующий элемент следует взять в середине этого сегмента: m = floor((L+R)/2), где L и R — текущие крайние выбранные позиции.
• После выбора m сегменты разбиваются на два: [L, m] и [m, R], и для каждого сегмента снова выбираем середину внутри него. Чтобы соблюдать правило «максимизировать минимальное расстояние» и ties по наиболее раннему в старом списке, используем приоритетную очередь (heap) по паре ключей:
  • основной ключ: максимальное расстояние d = floor((R-L)/2) внутри сегмента,
  • побочный ключ: минимальный индекс m внутри сегмента (чем меньше m, тем раньше в старом списке).
• Инициализируем результат двумя элементами: A[0] и A[N-1], затем запускаем обработку сегментов: сначала сегмент (0, N-1), затем делим его по выбранному m и добавляем новые сегменты в кучу.

Сложность: каждое добавление элемента требует извлечения и добавления в кучу, в сумме O(N log N). Память O(N).

Код на Python 3.11:

import sys
import heapq

def solve():
    data = list(map(int, sys.stdin.buffer.read().split()))
    if not data:
        return

    N = data[0]
    A = data[1:1+N]

    if N == 0:
        print()
        return
    if N == 1:
        print(A[0])
        return

    # Первый элемент нового списка совпадает с первым старого
    res = [A[0]]
    if N >= 2:
        res.append(A[N-1])

    if N <= 2:
        print(' '.join(map(str, res)))
        return

    # Максим-heap по сегментам: каждый сегмент задаётся (L, R) с выбранными концами L и R
    # Ключи: (-d, m, L, R) где d = floor((R-L)/2), m = floor((L+R)/2)
    heap = []
    L, R = 0, N - 1
    m0 = (L + R) // 2
    d0 = (R - L) // 2
    heapq.heappush(heap, (-d0, m0, L, R))

    while len(res) < N:
        negd, m, L, R = heapq.heappop(heap)
        res.append(A[m])

        # левая часть: (L, m)
        if m - L > 1:
            mL = (L + m) // 2
            dL = (m - L) // 2
            heapq.heappush(heap, (-dL, mL, L, m))

        # правая часть: (m, R)
        if R - m > 1:
            mR = (m + R) // 2
            dR = (R - m) // 2
            heapq.heappush(heap, (-dR, mR, m, R))

    print(' '.join(map(str, res)))

if __name__ == "__main__":
    solve()

Пояснения по ключам в куче:

• основной критерий — максимизация d = floor((R-L)/2) для сегмента (L, R). Чем больше d, тем предпочтительнее сегмент.
• при равенстве d выигрывает сегмент, у которого кандидат m меньше (меньший индекс в старом списке), что соответствует требованию «выбирается тот, который идёт раньше в старом списке».

Пример работы:

• Для N=5 и старого списка [a0, a1, a2, a3, a4]: 1)res = [a0, a4], сегмент (0,4) -> m=2 2)добавляем a2, сегменты (0,2) и (2,4)
  3. выбираем меньший m среди кандидатов: m=1, затем m=3 Итог: [a0, a4, a2, a1, a3].