Однажды в Тридевятом царстве, устав от безделья, богатырь Илья Муромец решил отправиться на танке в путешествие за Кудыкины горы. Он был полон решимости продемонстрировать свою интуицию, ум и находчивость в решении задач по информатике перед заморскими буржуинами и принцессами.
Шамаханская царица и массив девочек
Однако на перевале Кудыкиных гор его поджидала царица Шамаханская с массивом прекрасных девушек
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:
```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`.
---
Если нужно более подробно — скажите, я подготовлю объяснение шаг за шагом или разбор конкретных случаев.
