Профессор перед экзаменом попросил ассистента подготовить список номеров вопросов для каждого студента. Так как профессор планирует подробно спрашивать материал курса, то каждый список представляет собой перестановку всех номеров вопросов. Профессору не понравилось, что иногда в списке похожие темы встречаются близко к друг другу. Тогда он решил перемешать каждый список вопросов по следующим правилам: первый номер вопроса в новом списке совпадает с первым номером из старого списка; каждый последующий номер выбирается так, чтобы он максимизировал минимальное расстояние до уже выбранных номеров, если таких номеров несколько, то выбирается тот, который идёт раньше в старом списке вопросов. Попытавшись перемешать номера вопросов в одном из списков по описанным правилам, профессор понял, что не успеет перемешать все списки до экзамена. Помогите ему решить эту задачу. Формат входных данных В первой строке содержится одно натуральное число N ( 2 ≤ N ≤ 10 в 5 степени ) — число номеров вопросов в списке. Вторая строка содержит N натуральных чисел — перестановку номеров вопросов из старого списка.

Задача требует построить новую перестановку номеров вопросов по правилу максимизации минимального расстояния до уже выбранных номеров (расстояние 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 ```python 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) и повторяем процесс до будет выбран весь набор индексов. Если нужно, могу привести ещё несколько конкретных примеров или помочь адаптировать решение под другой язык программирования.