2025/26, Кружок для начинающих, Изучаем стек
A: Порстой стек
Реализуйте структуру данных "стек". Напишите программу, содержащую описание стека и моделирующую работу стека, реализовав все указанные здесь методы. Программа считывает последовательность команд и в зависимости от команды выполняет ту или иную операцию. После выполнения каждой команды программа должна вывести одну строчку. Возможные команды для программы:
push n
Добавить в стек число n (значение n задается после команды). Программа должна вывести ok.
pop
Удалить из стека последний элемент. Программа должна вывести его значение.
back
Программа должна вывести значение последнего элемента, не удаляя его из стека.
size
Программа должна вывести количество элементов в стеке.
clear
Программа должна очистить стек и вывести ok.
exit
Программа должна вывести bye и завершить работу.
Формат входных данных
Команды управления стеком вводятся в описанном ранее формате по 1 на строке.
Гарантируется, что набор входных команд удовлетворяет следующим требованиям: максимальное количество элементов в стеке в любой момент не превосходит 100, все команды pop и back корректны, то есть при их исполнении в стеке
содержится хотя бы один элемент.
Формат выходных данных
Tребуется вывести протокол работы со стеком, по 1 сообщению в строке
Примеры
| Ввод | Вывод |
|---|
push 1
back
exit |
ok
1
bye |
size
push 1
size
push 2
size
push 3
size
exit |
0
ok
1
ok
2
ok
3
bye |
B: Разверните последовательность
Вводится последовательность целых чисел, оканчивающаяся нулем. Число 0 в последовательность не входит.
Выведите элементы последовательности в обратном порядке. Для хранения данных используйте стек.
Формат входных данных
Вводится последовательность целых чисел, по модулю не превосходящих \(10000\). Ввод заканчивается, когда будет введено число \(0\). Всего чисел не более \(100\) (не считая нуля).
Формат выходных данных
Выведите элементы этой последовательности в обратном порядке, через пробел.
Пример
| Ввод | Вывод |
|---|
1 2 3 4 5 0 |
5 4 3 2 1 |
C: Правильная скобочная последовательность
Рассмотрим последовательность, состоящую из круглых, квадратных и фигурных скобок.
Программа дожна определить, является ли данная скобочная последовательность правильной.
Пустая последовательность явлется правильной. Если \(A\) – правильная, то последовательности \((A)\), \([A]\), \({A}\) – правильные.
Если \(A\) и \(B\) – правильные последовательности, то последовательность \(AB\) – правильная.
Формат входных данных
В единственной строке записана скобочная последовательность, содержащая не более \(100000\) скобок.
Формат выходных данных
Если данная последовательность правильная, то программа должна вывести строку yes, иначе строку no.
Примеры
| Ввод | Вывод |
|---|
()[] |
yes |
([)] |
no |
D: 5E: удалите скобки
Дана строка, составленная из круглых скобок. Определите, какое наименьшее количество символов необходимо удалить из этой строки, чтобы оставшиеся символы образовывали правильную скобочную последовательность.
Формат входных данных
Во входном файле записана строка из круглых скобок. Длина строки не превосходит \({100\,000}\) символов.
Формат выходных данных
Выведите единственное целое число — ответ на поставленную задачу.
Примеры
| Ввод | Вывод |
|---|
())(() |
2 |
))((( |
5 |
E: Постфиксная запись
В постфиксной записи (или обратной польской записи) операция записывается после двух операндов.
Например, сумма двух чисел \(A\) и \(B\) записывается как \(A\) \(B\) \(+\) . Запись \(B\) \(C\) \(+\) \(D\) \(*\) обозначает привычное нам \((B + C) * D\), а запись \(A\) \(B\) \(C\) \(+\) \(D\) \(*\) \(+\) означает \(A + (B + C) * D\) . Достоинство постфиксной записи в том, что она не требует скобок и дополнительных соглашений о приоритете операторов для своего чтения.
Формат входных данных
В единственной строке записано выражение в постфиксной записи, содержащее цифры и операции \(+\), \(-\), \(*\). Цифры и операции разделяются пробелами. В конце строки может быть произвольное количество пробелов.
Формат выходных данных
Необходимо вывести значение записанного выражения.
Примеры
| Ввод | Вывод |
|---|
8 9 + 1 7 - * |
-102 |
9 9 9 9 9 9 9 9 9 * * * * * * * * |
387420489 |
F: Сортировка вагонов
К тупику со стороны пути 1 (см. рисунок) подъехал поезд. Разрешается отцепить от поезда один или сразу несколько первых вагонов и завезти их в тупик (при желании, можно даже завезти в тупик сразу весь поезд). После этого часть из этих вагонов вывезти в сторону пути 2. После этого можно завезти в тупик еще несколько вагонов и снова часть оказавшихся вагонов вывезти в сторону пути 2. И так далее (так, что каждый вагон может лишь один раз заехать с пути 1 в тупик, а затем один раз выехать из тупика на путь 2). Заезжать в тупик с пути 2 или выезжать из тупика на путь 1 запрещается. Нельзя с пути 1 попасть на путь 2, не заезжая в тупик.
Известно, в каком порядке изначально идут вагоны поезда. Требуется с помощью указанных операций сделать так, чтобы вагоны поезда шли по порядку (сначала первый, потом второй и т.д., считая от головы поезда, едущего по пути 2 в сторону от тупика). Напишите программу, определяющую, можно ли это сделать.
Формат входных данных
Вводится число \(N\) — количество вагонов в поезде \((1 \le N \le 100)\). Дальше идут номера вагонов в порядке от головы поезда, едущего по пути 1 в сторону тупика. Вагоны пронумерованы натуральными числами от 1 до \(N\), каждое из которых встречается ровно один раз.
Формат выходных данных
Если сделать так, чтобы вагоны шли в порядке от \(1\) до \(N\), считая от головы поезда, когда поезд поедет по пути 2 из тупика, можно, выведите сообщение YES, если это сделать нельзя, выведите
NO.
Примеры
| Ввод | Вывод |
|---|
3
3 2 1 |
YES |
4
4 1 3 2 |
YES |
G: Великое Лайнландское переселение
Лайнландия представляет из себя одномерный мир, являющийся прямой, на котором распологаются \(N\) городов, последовательно пронумерованных от \(0\) до \( N - 1 \) . Направление в сторону от первого города к нулевому названо западным, а в обратную — восточным.
Когда в Лайнландии неожиданно начался кризис, все были жители мира стали испытывать глубокое смятение. По всей Лайнландии стали ходить слухи, что на востоке живётся лучше, чем на западе.
Так и началось Великое Лайнландское переселение. Обитатели мира целыми городами отправились на восток, покинув родные улицы, и двигались до тех пор, пока не приходили в город, в котором средняя цена проживания была меньше, чем в родном.
Формат входных данных
В первой строке дано одно число \(N\) \(( 2 \leq N \leq 10^{5} )\) — количество городов в Лайнландии. Во второй строке дано \(N\) чисел \(a_{i} (0 \le a_{i} \le 10^{9} )\) — средняя цена проживания в городах с нулевого по \(N-1\) соответственно.
Формат выходных данных
Для каждого города в порядке с нулевого по \(N - 1\) выведите номер города, в который переселятся его изначальные жители. Если жители города не остановятся в каком-либо другом городе, отправившись в Восточное Бесконечное Ничто, выведите -1.
Примеры
| Ввод | Вывод |
|---|
10
1 2 3 2 1 4 2 5 3 1 |
-1 4 3 4 -1 6 9 8 9 -1 |
10
65 51 79 36 2 47 92 30 25 94 |
1 3 3 4 -1 7 7 8 -1 -1 |
H: Гемоглобин
Каждый день к Грегори Хаусу приходит много больных, и у каждого измеряется уровень гемоглобина в крови. Данные по всем пациентам заносятся в базу данных.
Но волчанка попадается один раз на миллион, а работать с остальными неинтересно. Чтобы Хаус не выгонял больных, Кадди иногда запрашивает статистику по \( k \) последним больным: ей хочется знать сумму их уровня гемоглобина.
Также Хаус — мизантроп: он смотрит уровень гемоглобина больного, который поступил к нему позже всех, и, видя, что это точно не волчанка, выписывает его из больницы и удаляет информацию о нем из базы.
Автоматизацию процесса Хаус поручил Чейзу. Но Чейз почему-то не справился с этой задачей и попросил вас ему помочь.
Формат входных данных
Первой строкой входного файла задано число \(n\) \((1 \leq n \leq 100000)\) — число обращений к базе данных.
Запросы к базе выглядят следующим образом:
\(+\) \(x\) \(( 1 \leq x \leq 10^{9} )\) — добавить пациента с уровнем гемоглобинa \(x\) в базу, \(-\) — удалить последнего пациента из базы
\(?\) \(k\) \(( 1 \leq k \leq 100000 )\) — вывести суммарный гемоглобин последних \(k\) пациентов. Гарантируется, что \(k\) не превосходит число элементов в базе. Также гарантируется, что запросов на удаление к пустой базе не поступает.
Перед началом работы база данных пуста.
Формат выходных данных
Для каждого запроса "\(-\)" вывести уровень гемоглобина в крови пациента, а для каждого запроса "\(?\) \(k\)" — суммарный гемоглобин у последних k поступивших пациентов. Ответы выводите в порядке поступления запросов.
Примеры
| Ввод | Вывод |
|---|
7
+1
+2
+3
?2
-
-
?1 |
5
3
2
1 |
5
+5
?1
+2
-
- |
5
2
5 |
I: Программирование квадрокоптеров
Школьники готовятся к участию в соревновании по программированию квадрокоптеров. Квадрокоптер, который используется в соревновании, может выполнять две команды: подняться вверх на 1 метр и опуститься вниз на 1 метр. Команда подъёма обозначается символом «(», а команда спуска — символом «)».
Программа для квадрокоптера представляет собой последовательность команд. Программа считается корректной, если, начав её исполнение на уровне земли и выполнив последовательно все команды, квадрокоптер снова оказывается на уровне земли. При этом в процессе выполнения программы квадрокоптер не должен пытаться опуститься ниже уровня земли.
Например, следующие программы являются корректными: «()(())», «((()))». Программа «(((» не является корректной, поскольку квадрокоптер завершает ее выполнение на высоте 3 метра над уровнем земли, программа «())(» также не является корректной, поскольку при выполнении третьей команды квадрокоптер пытается опуститься ниже уровня земли.
Участник соревнования написал корректную программу для квадрокоптера, состоящую из \(n\) команд, пронумерованных от \(1\) до \(n\). Он загрузил её в память квадрокоптера для демонстрации во время соревнования. К сожалению, после загрузки программы в память квадрокоптера участник случайно удалил её на своём компьютере, а квадрокоптер не позволяет выгрузить программу из своей памяти.
К счастью, квадрокоптер поддерживает специальный режим отладки программы. В этом режиме квадрокоптер с загруженной в него программой может отвечать на специальные запросы. Каждый запрос представляет собой два целых числа: \(l\) и \(r\), \((1 \leq l \leq r \leq n)\). В ответ на запрос квадрокоптер сообщает, является ли фрагмент загруженной в него программы, состоящий из команд с \(l\)-й по \(r\)-ю включительно, корректной программой для квадрокоптера, либо нет. Участник хочет с помощью режима отладки восстановить загруженную в квадрокоптер программу.
Требуется написать программу-решение, которая взаимодействует с программой жюри, моделирующей режим отладки квадрокоптера, и в итоге восстанавливает загруженную в квадрокоптер программу.
Формат входных данных
Это интерактивная задача.
Сначала на вход подаётся целое число n — количество команд в программе квадрокоптера (2 ≤ n ≤ 50 000).
Для каждого теста жюри зафиксировано число k — максимальное количество запросов. Гарантируется, что k запросов достаточно, чтобы решить задачу. Это число не сообщается
программе-решению. Ограничения k в различных подзадачах приведены в таблице системы оценивания. Если программа-решение делает более k запросов к программе жюри,
то на этом тесте она получает в качестве результата тестирования «Неверный ответ».
Чтобы сделать запрос, программа-решение должна вывести строку вида «? l r», где l и
r — целые положительные числа, задающие фрагмент программы квадрокоптера (1 ≤ l ≤ r ≤ n).
В ответ на запрос программы-решения программа жюри подаёт ей на вход либо строку «Yes», либо строку «No», в зависимости от того, является ли запрошенный фрагмент
программы квадрокоптера корректной программой.
Если программа-решение определила ответ на задачу, то она должна вывести строку «! c1c2... cn»,
где символ ci задаёт i-ю команду в программе квадрокоптера и равен либо «(», либо «
)».
После этого программа-решение должна завершиться.
Гарантируется, что в каждом тесте программа в памяти квадрокоптера является фиксированной корректной программой, которая не меняется в зависимости от запросов, произведённых программой-решением.
Приведённые примеры иллюстрируют взаимодействие программы-решения с программой жюри «по шагам», для чего в них добавлены дополнительные пустые строки. При реальном тестировании лишние пустые строки вводиться не будут, выводить пустые строки
также не требуется.
В первом примере n = 4. Единственная возможная корректная программа из двух команд это «()», поэтому из результатов третьего и четвёртого запросов можно сделать вывод,
что программа в памяти квадрокоптера — «()()». Поэтому, в частности, ответ на второй запрос действительно «No», так как фрагмент программы «()(»
не является корректной программой: если квадрокоптер исполнит именно эти три команды, он останется на уровне одного метра над землёй.
В втором примере n = 6, и произведённых запросов достаточно, чтобы однозначно определить, что программа в памяти квадрокоптера — «((()))».
В тестах из условия k = 150, то есть, разрешается произвести не более 150 запросов.