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

Задача требует построить новую перестановку номеров вопросов по правилу максимизации минимального расстояния до уже выбранных номеров (расстояние measured по позициям в старом списке). В старом списке позиции идут как индексы 0..N-1, а расстояние между двумя номерами равно абсолютной разности их позиций в старом списке. Первый элемент новой перестановки должен совпадать с первым элементом старого списка. Далее каждый следующий элемент выбирается так, чтобы минимальное расстояние до уже выбранных было максимальным; в случае равенства расстояний выбрать элемент, который идёт раньше в старом списке.

Ключевые идеи

• Пусть выбранные индексы в старом списке записаны как L = {i0, i1, ..., ik} по возрастанию. Для любого непосещённого индекса i расстояние до ближайшего выбранного равно min_j |i - i_j|.
• Первый выбранный после i0 = 0 — это i1 = N-1 (самый дальний от 0).
• После выбора концов 0 и N-1 остаётся набор промежутков между соседними выбранными индексами: (0, N-1) → внутри этого промежутка можно выбрать i = floor((0 + (N-1)) / 2) как оптимальный по D = floor((N-1)/2). Затем промежуток разбивается на два: (0, i) и (i, N-1), и т.д.
• Если у нескольких промежутков одинаково D, выбор идёт в пользу меньшего i, то есть более левого середины. Это можно реализовать через структуру данных, которая хранит в качестве ключа пары: D по убыванию и i по возрастанию.

Алгоритм

1. Выводим первый элемент: a[0].
2. Если N > 1, выводим второй элемент: a[N-1].
3. После этого держим Max-Heap (или практически на Python — min-heap с ключами (-D, i, left, right)) для интервалов между соседними выбранными индексами. После первых двух выбранных индексов у нас есть один интервал (0, N-1) с D = floor((N-1)/2) и candidate i = floor((0 + (N-1)) / 2).
4. Пока не выбрано все N элементов:
   • Берём интервал с максимальным D и, при равных D, минимальным i.
   • Пусть этот интервал слева и справа — (left, right). Выбираем i = floor((left + right) / 2).
   • Добавляем a[i] в результат.
   • Разбиваем интервал на два: (left, i) и (i, right). Для каждого, если в нём ещё есть непосещённые элементы (разность right-left > 1), добавляем соответствующий новый промежуток в кучу со своим D и своим i-серединой.
5. В результате получаем новую перестановку чисел.

Сложность

• В худшем случае каждый элемент добавляется в результат ровно один раз.
• Операции в куче выполняются O(log N) раз для каждого элемента.
• В целом время O(N log N), память O(N).

Пример

• Пусть N = 5 и старый список a = [1, 2, 3, 4, 5].
  • Шаг 0: 1
  • Шаг 1: 5
  • Промежуток (0,4): i = floor((0+4)/2) = 2
  • Промежутки: (0,2) и (2,4). У обоих D = 1, выбор меньшего i => i = 1
  • Затем остаётся промежуток (2,4) с i = 3
  • Итого: 1, 5, 3, 2, 4

Письменный код на Python 3

import sys
import heapq

def main():
    data = sys.stdin.read().strip().split()
    if not data:
        return
    it = iter(data)
    N = int(next(it))
    a = [int(next(it)) for _ in range(N)]

    # Результат: номера вопросов в новой последовательности
    res = []
    res.append(a[0])  # первый номер совпадает с первым из старого списка

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

    res.append(a[N-1])  # второй номер: крайний справа

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

    # Читаем индексы, которые уже выбраны
    chosen = [False] * N
    chosen[0] = True
    chosen[N-1] = True

    # Куча промежутков между соседними выбранными индексами
    # Элемент кучи: (-D, i_mid, left, right)
    # где i_mid = floor((left+right)/2), D = floor((right-left)/2)
    heap = []
    left, right = 0, N - 1
    if right - left > 1:
        D = (right - left) // 2
        i_mid = (left + right) // 2
        heap.append((-D, i_mid, left, right))
        heapq.heapify(heap)

    # Пока не выбрали все элементы
    while len(res) < N:
        if not heap:
            # Теоретически не должны возникнуть в этой задаче
            break
        negD, i_mid, left, right = heapq.heappop(heap)
        if chosen[i_mid]:
            # Пропустим, если уже было выбрано (на случай дубликатов в куче)
            continue

        # Выбираем этот индекс
        chosen[i_mid] = True
        res.append(a[i_mid])

        # Разбиваем интервал на два: (left, i_mid) и (i_mid, right)
        # Первый новый интервал
        if i_mid - left > 1:
            D1 = (i_mid - left) // 2
            i1 = (left + i_mid) // 2
            heapq.heappush(heap, (-D1, i1, left, i_mid))
        # Второй новый интервал
        if right - i_mid > 1:
            D2 = (right - i_mid) // 2
            i2 = (i_mid + right) // 2
            heapq.heappush(heap, (-D2, i2, i_mid, right))

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

if __name__ == "__main__":
    main()

Пояснение по коду

• Мы сначала выводим a[0], затем a[N-1]. После этого создаём один промежуток между этими двумя выбранными индексами: (0, N-1). В нём оптимальный следующий индекс — floor((0 + (N-1)) / 2).
• Далее в куче хранятся промежутки между соседними выбранными индексами. Для каждого такого промежутка (left, right) следующий индекс внутри него — i_mid = floor((left+right)/2), с расстоянием D = floor((right-left)/2). Мы сортируем по D убыванию, а при равных D — по i_mid возрастанию (это соответствует правилу: выбрать тот, который идёт раньше в старом списке).
• При выборе i_mid мы добавляем новые промежутки (left, i_mid) и (i_mid, right) и повторяем процесс до будет выбран весь набор индексов.

Если нужно, могу привести ещё несколько конкретных примеров или помочь адаптировать решение под другой язык программирования.