Однажды в Тридевятом царстве, устав от безделья, богатырь Илья Муромец решил отправиться на танке в путешествие за Кудыкины горы. Он был полон решимости продемонстрировать свою…
Однажды в Тридевятом царстве, устав от безделья, богатырь Илья Муромец решил отправиться на танке в путешествие за Кудыкины горы. Он был полон решимости продемонстрировать свою интуицию, ум и находчивость в решении задач по информатике перед заморскими буржуинами и принцессами. Шамаханская царица и массив девочек Однако на перевале Кудыкиных гор его поджидала царица Шамаханская с массивом прекрасных девушек a i a i длиной n n. Богатырь понял, что не сможет продолжить свой путь и показать свою силу в информатике, пока не решит задачу с этим массивом. И тогда Илья Муромец взял пустой массив b b и приступил к выполнению следующих n n действий. Для каждого i i от 1 1 до n n богатырь Илья: Добавляет a i a i в конец массива b b. Разворачивает порядок элементов в массиве b b. Помогите богатырю Илье вывести массив b b после всех n n действий. Формат ввода Первая строка содержит целое число n n ( 1 ≤ n ≤ 2 × 1 0 5 1≤n≤2×10 5 ). Вторая строка содержит n n целых чисел a i a i ( 0 ≤ a i ≤ 1 0 9 0≤a i ≤10 9 ). Формат вывода Выведите n n целых чисел в одной строке, где i i-е число соответствует элементу b i b i в массиве b b после выполнения всех n n действий богатыря Ильи Муромца. Система оценивания Первая группа тестов для n ≤ 100 n≤100 – 16 баллов. Вторая группа тестов для a i ≤ 1 0 6 a i ≤10 6 – 24 балла. Третья группа тестов – нет ограничений – 60 баллов. Пример 1 Ввод Вывод 4 1 2 3 4 4 2 1 3 Пример 2 Ввод Вывод 3 1 2 3 3 1 2 Пример 3 Ввод Вывод 6 3 8 5 3 9 1 1 3 8 3 5 9
Задача, которую вы описали, связана с обработкой массива с последовательными операциями — добавлением элемента, затем разворотом массива. После выполнения всех действий нам нужно вывести итоговый массив.
Основная идея:
- Добавлять элементы по одному.
- После каждого добавления — разворачивать массив.
- После выполнения всех операций выводить полученный массив.
Проблема:
Прямое выполнение таких операций (каждый раз разворачивая массив) будет очень неэффективным для больших n, поскольку это приведет к больших затратам по времени (O(n^2)).
Оптимизация:
- Можно моделировать действия более эффективно, не используя постоянные развороты.
- Заметим, что после каждого добавления и разворота, позиция элементов меняется. В итоге, когда мы рассматриваем весь процесс, он сводится к тому, чтобы понять, как меняется порядок элементов после всех этих операций.
Подход:
Мы можем хранить объекты в виде двух "стеков" или двух концов очереди, которые позволяют моделировать такие действия быстрее.
В данном случае удобнее всего работать с двумя-деками (двухсторонняя очередь):
- Если операция — вставка элемента в конец и разворот, то можно подумать так:
- После добавления элемента и разворота, фактически, текущий массив меняется на противоположный порядок с добавленным новым элемент на другую сторону.
- Если операция — вставка элемента в конец и разворот, то можно подумать так:
В конечном итоге, можно реализовать так:
- Поддерживать два указателя или две коллекции (например, deque).
- В зависимости от количества операций, можно хранить либо "обычный" порядок, либо "обратный" порядок.
- После всех операций определить финальный порядок и вывести результат.
Реализация:
- Введем переменную
reverse_flag, которая будет показывать, в каком порядке сейчас находится массив. - Для каждого элемента:
- Если
reverse_flag— False, добавлять элемент слева (в конце). - Если True, добавлять элемент справа (в начало).
- Если
- После каждого добавления менять
reverse_flag. - В конце, если
reverse_flag— True, то массив нужно вывести в обратном порядке, иначе — так, как есть.
Пример кода на Python:
from collections import deque
n = int(input())
a = list(map(int, input().split()))
b = deque()
reverse_flag = False
for ai in a:
if not reverse_flag:
# добавляем в конец
b.append(ai)
else:
# добавляем в начало
b.appendleft(ai)
# разворачиваем массив
reverse_flag = not reverse_flag
# если последний `reverse_flag` — True, значит финальный порядок — обратный
if reverse_flag:
b.reverse()
print(' '.join(map(str, b)))
Почему это работает?
- Каждый раз добавляем к "концу" или "началу" в зависимости от флага.
- В конце — при необходимости — переворачиваем весь массив, что делается за O(n).
- Время выполнения — O(n), что подходит для больших
n.
Если нужно более подробно — скажите, я подготовлю объяснение шаг за шагом или разбор конкретных случаев.
