- A
- B
- C
- D
- E
- F
- G
- H
- I
Стеки, очереди, СНМ
A. Минимум на стеке
Ограничение по времени на тест: 2 секунды
Ограничение по памяти на тест: 256 мегабайт
Вам требуется реализовать структуру данных, выполняющую следующие операции:
- Добавить элемент $x$ в конец структуры.
- Удалить последний элемент из структуры.
- Выдать минимальный элемент в структуре.
Входные данные
В первой строке входного файла задано одно целое число $n$ — количество операций $(1 ⩽ n ⩽ 10^6)$. В следующих $n$ строках заданы сами операции. В $i$–ой строке число $t_i$ — тип операции (1, если операция добавления. 2, если операция удаления. 3, если операция минимума). Если задана операция добавления, то через пробел записано целое число $x$ — элемент, который следует добавить в структуру $(−10^9 ⩽ x ⩽ 10^9)$. Гарантируется, что перед каждой операцией удаления или нахождения минимума структура не пуста.
Выходные данные
Для каждой операции нахождения минимума выведите одно число — минимальный элемент в структуре. Ответы разделяйте переводом строки.
Пример
Входные данные
8
1 2
1 3
1 -3
3
2
3
2
3
Выходные данные
-3
2
2
Решение
B. Шарики
Ограничение по времени на тест: 2 секунды
Ограничение по памяти на тест: 256 мегабайт
В одной компьютерной игре игрок выставляет в линию шарики разных цветов. Когда образуется непрерывная цепочка из трех и более шариков одного цвета, она удаляется из линии. Все шарики при этом сдвигаются друг к другу, и ситуация может повториться.
Напишите программу, которая по данной ситуации определяет, сколько шариков будет сейчас уничтожено. Естественно, непрерывных цепочек из трех и более одноцветных шаров в начальный момент может быть не более одной.
Входные данные
Даны количество шариков в цепочке (не более $10^5$) и цвета шариков (от 0 до 9, каждому цвету соответствует свое целое число).
Выходные данные
Требуется вывести количество шариков, которое будет уничтожено.
Пример
Входные данные
5 1 3 3 3 2
Выходные данные
3
Входные данные
10 3 3 2 1 1 1 2 2 3 3
Выходные данные
10
Решение
C. Астроград
Ограничение по времени на тест: 1 секунда
Ограничение по памяти на тест: 256 мегабайт
В Астрополисе прошел концерт популярной группы Астроград. За пару дней до концерта перед кассой выстроилась огромная очередь из людей, желающих туда попасть. Изначально очередь была пуста. В каждый из $n$ моментов времени происходило следующее:
- В очередь пришел новый человек с уникальным номером $id$, он встает в очередь последним.
- Человеку, стоящему спереди очереди, удалось купить билет. Он уходит.
- Человеку, стоящему последнему в очереди, надоело ждать. Он уходит.
- Человек с уникальным номером $q$ хочет знать, сколько людей стоит в очереди спереди него.
- Очередь хочет знать, человек с каким уникальным номером стоит сейчас первым и задерживает всех.
Вам необходимо написать программу, которая умеет обрабатывать описанные события.
Входные данные
В первой строке дано целое число $n$ $(1 ⩽ n ⩽ 10^5)$ — количество событий. В каждой из следующих $n$ строк дано описание событий: номер события, а также число $id$ $(1 ⩽ id ⩽ 10^5)$ для событий типа 1 и число $q$ для событий типа 4. События происходили в том порядке, в каком они описаны во входном файле. Гарантируется корректность всех событий.
Выходные данные
Выведите ответы для событий типа 4 и 5 в том порядке, в каком они описаны во входном файле.
Пример
Входные данные
7
1 1
5
1 3
3
2
1 2
4 2
Выходные данные
1
0
Примечание
В примере из условия происходили следующие события:
- В очередь пришел человек с $id = 1$. Очередь:
[ 1 ] - Первым в очереди стоит человек с $id = 1$. Очередь:
[ 1 ] - В очередь пришел человек с $id = 3$. Очередь:
[ 1, 3 ] - Последнему в очереди надоело стоять и он уходит. Очередь:
[ 1 ] - Первому в очереди удалось купить билет и он уходит. Очередь:
[ ] - В очередь пришел человек с $id = 2$. Очередь:
[ 2 ] - $q = 2$ хочет знать, сколько человек стоит перед ним. Очередь:
[ 2 ]
Решение
D. Гоблины и шаманы
Ограничение по времени на тест: 2 секунды
Ограничение по памяти на тест: 256 мегабайт
Гоблины Мглистых гор очень любят ходить к своим шаманам. Так как гоблинов много, к шаманам часто образуются очень длинные очереди. А поскольку много гоблинов в одном месте быстро образуют шумную толпу, которая мешает шаманам проводить сложные медицинские манипуляции, последние решили установить некоторые правила касательно порядка в очереди.
Обычные гоблины при посещении шаманов должны вставать в конец очереди. Привилегированные же гоблины, знающие особый пароль, встают ровно в ее середину, причем при нечетной длине очереди они встают сразу за центром.
Так как гоблины также широко известны своим непочтительным отношением ко всяческим правилам и законам, шаманы попросили вас написать программу, которая бы отслеживала порядок гоблинов в очереди.
Входные данные
В первой строке входных данный записано число $N$ $(1 ⩽ N ⩽ 5 \cdot 10^5)$ — количество запросов к программе. Следующие $N$ строк содержат описание запросов в формате:
- "+ $i$" - гоблин с номером $i$ $(1 ⩽ i ⩽ N)$ встает в конец очереди.
- "* $i$" - привилегированный гоблин с номером $i$ встает в середину очереди.
- "-" - первый гоблин из очереди уходит к шаманам. Гарантируется, что на момент такого запроса очередь не пуста.
Выходные данные
Для каждого запроса типа "-" программа должна вывести номер гоблина, который должен зайти к шаманам.
Пример
Входные данные
7
+ 1
+ 2
-
+ 3
+ 4
-
-
Выходные данные
1
2
3
Решение
E. Постфиксная запись
Ограничение по времени на тест: 1 секунда
Ограничение по памяти на тест: 256 мегабайт
В постфиксной записи (или обратной польской записи) операция записывается после двух операндов. Например, сумма двух чисел $A$ и $B$ записывается как A B +. Запись B C + D * обозначает привычное нам (B + C) * D, а запись A B C + D * + означает A + (B + C) * D. Достоинство постфиксной записи в том, что она не требует скобок и дополнительных соглашений о приоритете операторов для своего чтения.
Дано выражение в обратной польской записи. Определите его значение.
Входные данные
В единственной строке записано выражение в постфиксной записи, содержащее однозначные числа и операции +, -, *. Строка содержит не более 100 чисел и операций.
Выходные данные
Необходимо вывести значение записанного выражения. Гарантируется, что результат выражения, а также результаты всех промежуточных вычислений по модулю меньше $2^{31}$.
Пример
Входные данные
8 9 + 1 7 - *
Выходные данные
-102
Решение
F. Сортировка стеком
Ограничение по времени на тест: 1 секунда
Ограничение по памяти на тест: 256 мегабайт
Пример
Входные данные
5
5 3 1 2 4
Выходные данные
push
push
push
pop
push
pop
pop
push
pop
pop
Входные данные
3
2 3 1
Выходные данные
impossible
Решение
G. Система непересекающихся множеств
Ограничение по времени на тест: 2 секунды
Ограничение по памяти на тест: 256 мегабайт
Реализуйте систему непересекающихся множеств. Вместе с каждым множеством храните минимальный, максимальный элемент в этом множестве и их количество.
Входные данные
Первая строка входного файла содержит $n$ — количество элементов в носителе $(1 ⩽ n ⩽ 300\ 000)$. Далее операций с множеством. Операция get должна возвращать минимальный, максимальный элемент в соответствующем множестве, а также их количество.
Выходные данные
Выведите последовательно результат выполнения всех операций get.
Пример
Входные данные
5
union 1 2
get 3
get 2
union 2 3
get 2
union 1 3
get 5
union 4 5
get 5
union 4 1
get 5
Выходные данные
3 3 1
1 2 2
1 3 3
5 5 1
4 5 2
1 5 5
Решение
H. Подсчет опыта
Ограничение по времени на тест: 2 секунды
Ограничение по памяти на тест: 256 мегабайт
В очередной онлайн игре игроки, как обычно, сражаются с монстрами и набирают опыт. Для того, чтобы сражаться с монстрами, они объединяются в кланы. После победы над монстром, всем участникам клана, победившего его, добавляется одинаковое число единиц опыта. Особенностью этой игры является то, что кланы никогда не распадаются и из клана нельзя выйти. Единственная доступная операция — объединение двух кланов в один.
Поскольку игроков стало уже много, вам поручили написать систему учета текущего опыта игроков.
Входные данные
В первой строке входного файла содержатся числа $n$ $(1 ⩽ n ⩽ 200\ 000)$ и $m$ $(1 ⩽ m ⩽ 200\ 000)$ — число зарегистрированных игроков и число запросов.
В следующих $m$ строках содержатся описания запросов. Запросы бывают трех типов:
join X Y— объединить кланы, в которые входят игроки $X$ и $Y$ (если они уже в одном клане, то ничего не меняется).add X V— добавить $V$ единиц опыта всем участникам клана, в который входит игрок $X$ $(1 ⩽ V ⩽ 100)$.get X— вывести текущий опыт игрока $X$.
Изначально у всех игроков 0 опыта и каждый из них состоит в клане, состоящим из него одного.
Выходные данные
Для каждого запроса get $X$ выведите текущий опыт игрока $X$.
Пример
Входные данные
3 6
add 1 100
join 1 3
add 1 50
get 1
get 2
get 3
Выходные данные
150
0
50
Решение
I. Кукушки
Ограничение по времени на тест: 2 секунды
Ограничение по памяти на тест: 512 мегабайт
Британские учёные решили заняться орнитологией и понаблюдать за жизнью необычных кукушек. Для этого они вырастили дерево и построили на нём $n$ гнёзд, в каждом из которых живёт кукушка. Наблюдение за деревом состоит в том, что в некоторые моменты времени учёные оценивают, можно ли подложить определённое яйцо в гнездо к некоторой кукушке или нет.
Каждое яйцо может вынашиваться только в двух определённых гнёздах. Каждое яйцо задаётся неупорядоченной парой различных чисел $(x, y)$. Яйцо $(x, y)$ может вынашиваться в любом из гнёзд $x$ и $y$ и не может вынашиваться в других гнёздах. Обратите внимание, яйцо $(x, y)$ не отличается от яйца $(y, x)$.
Теперь опишем процесс подкладывания яйца в имеющиеся гнезда: пусть учёные хотят подложить яйцо $(x, y)$ в гнездо $x$. Если в гнезде $x$ нет яйца, то яйцо $(x, y)$ просто остаётся в этом гнезде, и процесс на данном шаге завершается. Если же в гнезде $x$ лежит какое-то яйцо $(x, p)$, то кукушка кладёт яйцо $(x, y)$ в данное гнездо, а яйцо $(x, p)$ пытается подложить в гнездо $p$ аналогичным образом, и процесс продолжается.
Вам предлагается отвечать на вопросы учёных. Всего есть три типа вопросов:
- (Теоретический) Закончится ли процесс, если подложить яйцо $(x, y)$ в гнездо $x$? Так как вопрос чисто теоретический, оно не добавляется на самом деле, и состояние гнёзд не меняется.
- (Практический) Закончится ли процесс, если подложить яйцо $(x, y)$ в гнездо $x$? Если процесс закончится, то яйцо добавляется в реальности согласно описанному процессу.
- (Теоретический) Сколько существует упорядоченных пар чисел $(x, y)$, таких что яйцо $(x, y)$ можно подложить в гнездо $x$ c учётом имеющихся в гнёздах яиц? При этом для каждого яйца ответ определяется независимо от других добавляемых яиц.
Входные данные
В первой строке вводятся три целых числа $n$, $m$, $q$, $(2 ⩽ n ⩽ 200\ 000,$ $0 ⩽ m ⩽ n,$ $1 ⩽ q ⩽ 600\ 000)$, где $n$ — количество гнёзд на дереве, $m$ — количество яиц, которые учёные уже положили, $q$ — количество вопросов, которые задают учёные.
В каждой из $m$ последующих строк следуют по два числа $x_i$, $y_i$, означающих, что в гнезде $x_i$ лежит яйцо $(x_i, y_i)$. Гарантируется, что все $x_i$ различны и что $x_i ≠ y_i$ для всех $i$.
В следующих $q$ строках описаны вопросы учёных. Вопросы даны в том порядке, в котором на них требуется отвечать. Первое число $t_j$ в строке описывает тип вопроса.
Если $t_j = 1$ или $t_j = 2$, то далее идут два различных числа $x_j$ и $y_j$, описывающих яйцо, которое фигурирует в соответствующем вопросе.
Если $t_j = 1$, то яйцо не требуется добавлять в текущую расстановку.
Если $t_j = 2$, то яйцо требуется добавить, если процесс добавления потребует конечного числа перекладываний.
Если $t_j = 3$, то требуется определить количество упорядоченных пар $(x, y)$, таких что яйцо $(x, y)$ можно добавить в гнездо $x$ с тем, чтобы процесс когда-нибудь завершился. В реальности никакие яйца в расстановку не добавляются.
Выходные данные
Для каждого вопроса первого и второго типа выведите единственное слово Yes или No в зависимости от того, закончится ли процесс перекладывания.
Для каждого запроса третьего типа выведите количество искомых упорядоченных пар.
Пример
Входные данные
5 3 8
1 2
5 1
2 4
1 1 2
3
2 1 2
3
2 4 2
2 5 3
3
1 4 5
Выходные данные
Yes
20
Yes
8
No
Yes
0
No
Примечание
Изначальное расположение яиц в тесте из условия такое: в первом гнезде лежит яйцо $(1, 2)$, во втором — $(2, 4)$, в пятом — $(5, 1)$, а в третьем и четвёртом яиц нет.
Яйцо $(1, 2)$ добавить можно, несмотря на то что подобное яйцо на дереве уже есть, это приведёт к перекладыванию имеющегося яйца $(1, 2)$ в другое гнездо.
Также в начальную конфигурацию можно добавить любое из 10 яиц, существующих для дерева с пятью гнёздами, и каждое яйцо можно положить в любое из двух гнёзд, ему отвечающих, и для любого из добавляемых яиц и гнёзд это потребует конечное количество шагов. Таким образом, ответ на второй запрос — 20.
В результате следующего запроса яйцо $(1, 2)$ будет добавлено реально, и распределение яиц будет таким: в первом гнезде лежит яйцо $(1, 2)$, во втором — также $(1, 2)$, в четвёртом — $(2, 4)$, в пятом $(5, 1)$.
Теперь уже можно добавить только яйца $(1, 3)$, $(2, 3)$, $(4, 3)$ и $(5, 3)$, причём по-прежнему любое яйцо можно положить в каждое из двух упомянутых на нём гнёзд, поэтому ответ на запрос — 8.
Яйцо $(4, 2)$ добавить на дерево нельзя, поэтому состояние гнёзд не изменится.
Для добавления яйца $(5, 3)$ понадобится 5 перекладываний яиц, а после этого никакое новое яйцо за конечное количество шагов добавить уже нельзя.