Во время каникул в Санкт-Петербурге Арина посетила выставку художников-импрессионистов. Для полноты восприятия она взяла аудиогид, чтобы не просто рассматривать картины, но и узнавать что-то новое.
Выставка представляет собой галерею из $$$n$$$ картин, развешанных (по порядку, от первой к $$$n$$$-й) на одной стене музея.
Арина хотела один раз пройтись по галерее, от картины с номером $$$1$$$ до картины с номером $$$n$$$, но в её планы вмешались другие любители живописи, стоявшие у некоторых картин. Поэтому, если у картины уже стоял посетитель, Арина пропускала её и шла дальше. Дойдя до конца галереи, она развернулась и продолжила осмотр, пользуясь той же тактикой относительно остальных посетителей, но в этот раз останавливаться только у ещё не просмотренных картин. Таким образом ей пришлось несколько раз пройти от одного конца галереи до другого. Посмотрев последнюю картину Арина продолжила движение в том же направлении и вышла из музея.
После культурной прогулки Арина решила посчитать сколько же раз она прошла по галерее. На её удачу в памяти аудиогида сохранилась последовательность треков с номерами картин.
Помогите Арине — по последовательности номеров картин определите, какое минимальное количество раз она прошла вдоль галереи.
В первой строке содержится целое число $$$n$$$ $$$(1 \le n \le 10^5)$$$ — количество картин в галерее.
Во второй строке содержится $$$n$$$ целых чисел $$$a_i$$$ $$$(1 \le a_i \le n)$$$ — номера картин в порядке их просмотра по истории аудиогида. Гарантируется, что $$$a_i \not= a_j$$$, если $$$i \not= j$$$.
Выведите единственное целое число — минимально возможное количество раз, которое Арина прошла вдоль галереи.
$$$$$$\begin{array}{|c|c|c|c|c|} \hline \text { Подзадача } & \text { Баллы } & \text { Ограничения } & \text { Оценка } & \text { Необходимые подзадачи } \\ \hline 0 & 0 & \text { Тесты из условия } & \text { подзадача } & \\ \hline 1 & 10 & n \le 10 &\text { подзадача } & \\ \hline 2 & 30 & n \le 1000 & \text { подзадача } & 1 \\ \hline 3 & 30 & n \le 50 000 & \text { подзадача } & 1, 2 \\ \hline 4 & 30 & \text{ Без дополнительных ограничений } & \text { подзадача } & 1, 2, 3 \\ \hline \end{array}$$$$$$
8
3 5 7 1 6 4 8 2
6
Поясним приведённый пример.
Сначала Арина движется по направлению «от первой картины к последней» и смотрит картины 3, 5, 7.
Дойдя до конца аллеи, она поворачивает и возвращается назад, чтобы посмотреть на 1 картину.
Снова повернув, она отправляется смотреть на 6 картину.
Ещё один поворот — и она приходит к 4 картине.
Затем ей приходится повернуть ещё один раз, чтобы дойти до 8 картины.
После этого необходимо вернуться к картине номер 2.
Никита учится на третьем курсе университета и очень любит смотреть аниме. А сейчас как раз сентябрь — самое время для Наруто. Никита уже настроился посмотреть пару десятков серий, как вдруг ему начали приходить электронные письма с домашками. Каждое письмо содержит собственно домашнее задание и дедлайн — 23:59 одного из последующих дней. Все домашки Никита делает непосредственно в день дедлайна, и выполнение заданий занимает весь день, независимо от их количества (если, например, в какой-то день дедлайн у пяти домашек, Никита сделает их все за этот день, просто не очень старательно).
Изначально Никита планировал посмотреть аниме завтра (в день с номером 1), но каждое приходящее письмо могло изменить его план (например, если пришло письмо с дедлайном в 23:59 первого дня, и такое бывает). После прочтения каждого письма, Никита вносит новое дз в своё расписание, а также корректирует план по просмотру аниме (если нужно).
Помогите Никите автоматизировать этот процесс: после каждого полученного письма выведите ближайший день, свободный от домашек, в который Никита сможет посмотреть Наруто.
В первой строке дано одно целое число $$$q$$$ ($$$1 \le q \le 10^5$$$) — число писем, полученных Никитой.
В следующей строке дано $$$q$$$ целых чисел $$$d_i$$$ ($$$1 \le d_i \le 10^9$$$) — день, на который назначен дедлайн в $$$i$$$-м письме.
Выведите $$$q$$$ целых чисел: для каждого $$$i \le q$$$ ближайший день, свободный от домашек, назначенных в первых $$$i$$$ письмах.
$$$$$$\begin{array}{|c|c|c|c|c|} \hline \text { Подзадача } & \text { Баллы } & \text { Ограничения } & \text { Оценка } & \text { Необходимые подзадачи } \\ \hline 0 & 0 & \text { Тесты из условия } & \text { подзадача } & \\ \hline 1 & 19 & q \le 100, d_i \le 100, \text { Все $d_i$ различны} & \text { подзадача } & \\ \hline 2 & 12 & q \le 100, d_i \le 100 & \text { подзадача } & 1 \\ \hline 3 & 26 & q \le 10^5, d_i \le 100 & \text { подзадача } & 1, 2 \\ \hline 4 & 43 & \text{ Без дополнительных ограничений } & \text { подзадача } & 1, 2, 3 \\ \hline \end{array}$$$$$$
5 1 3 2 6 4
2 2 4 4 5
Сегодня Полина со своими сокомандниками написала 5-часовую тренировку в школе и теперь собирается возвращаться домой. К сожалению, на улице пошёл дождь, а зонт девочка, как обычно, не взяла. К счастью, у неё есть приложение, показывающее не только погоду, но и интенсивность осадков, которым она сейчас и собирается воспользоваться, чтобы промокнуть как можно меньше (хотя могла бы воспользоваться им утром и просто взять зонт, но это слишком просто).
Обычно, возвращаясь из школы, Полина сначала идёт по «обычной» улице, а затем по аллее сквера, которую укрывают деревья с раскидистой кроной. Крона деревьев сможет задержать часть капель, что позволит Полине меньше намокнуть.
Время, в течение которого Полина будет идти по «обычной» улице, составляет $$$t_1$$$ минут, затем в течение времени $$$t_2$$$ минут она будет идти под деревьями (пока не дойдёт до дома).
Полине нужно оказаться дома не позднее, чем через $$$d$$$ $$$(t_1 + t_2 \le d)$$$ единиц времени от текущего момента (иначе она опоздает на ужин).
Полинино приложение говорит, что в $$$j$$$-ю минуту интенсивность дождя составляет $$$r_j$$$. Крона деревьев снижает интенсивность дождя на величину $$$s$$$ (но не может сделать её отрицательной).
Полина хочет минимизировать суммарную интенсивность дождя, прольющегося на неё.
Ваша задача — определить, в какой момент Полине следует выйти из школы, а также суммарную интенсивность дождя, которая ей достанется в этом случае.
В первой строке содержатся целые числа $$$t_1$$$, $$$t_2$$$, $$$d$$$, $$$s$$$ $$$(1 \le t_1, \, t_2, \, d \le 10^6, \, t_1 + t_2 \le d, \, 1 \le s \le 10^5)$$$, $$$t_1$$$ — время пути по «обычной» улице; $$$t_2$$$ — время пути по аллее, $$$d$$$ — момент времени, не позже которого Полина должна оказаться дома, $$$s$$$ — величина уменьшения интенсивности дождя под кронами.
Во второй строке содержится $$$d$$$ целых чисел $$$r_1, r_2, \ldots, r_d$$$ $$$(1 \le r_j \le 10^5, \, j = 1, 2, \ldots, d)$$$ — интенсивность дождя.
Выведите два целых числа: момент времени, в который Полине следует выйти из школы, и суммарную интенсивность дождя, под которым она пройдёт.
Если существует несколько вариантов ответа, выведите наиболее ранний момент времени.
$$$$$$\begin{array}{|c|c|c|c|c|} \hline \text { Подзадача } & \text { Баллы } & \text { Ограничения } & \text { Оценка } & \text { Необходимые подзадачи } \\ \hline 0 & 0 & \text { Тесты из условия } & \text { подзадача } \\ \hline 1 & 28 & \text {Входные данные не превышают 100 } & \text { подзадача } \\ \hline 2 & 45 & t_1, t_2, d \le 10^5 & \text { подзадача } & 1 \\ \hline 3 & 27 & \text{ Без дополнительных ограничений } & \text { подзадача } & 1, 2 \\ \hline \end{array}$$$$$$
2 3 10 5 1 1 1 8 7 1 1 2 10 1
0 7
5 7 17 6 5 7 8 4 2 2 7 6 5 7 4 8 8 7 3 6 1
3 27
Маленькая Саша любит играть с папой в города. За последние дни они уже сыграли целых $$$N$$$ партий. Каждую игру начинал папа, но выигрывала Саша. Поэтому у Саши появилось подозрение — а вдруг папа ей поддается?
У Саши очень хорошая память: она помнит всё о каждой из игр, а именно: что в игре с номером $$$i$$$ всего было названо $$$M_i$$$ городов, а также сами города в правильном порядке. Напомним, что по правилам игры, первая буква названия каждого следующего города должна совпадать с последней буквой названия предыдущего, и никакой город не может быть назван дваджы.
У папы тоже отличная память, и если в какой-либо игре был назван город, то во всех последующих партиях он будет его помнить и сможет назвать его в свой ход. Помогите Саше узнать, достаточно ли этих данных чтобы определить, поддавался ли папа (т.е. была ли такая ситуация, в которой он мог назвать известный ему по предыдущим играм город, но сдался). В случае, если папа поддался, выведите также город, который он мог бы назвать в свой следущий ход.
В первой строке дано одно целое число $$$n$$$ — количество партий $$$(2 \le n \le 10^5)$$$.
Далее следует описание $$$n$$$ игр.
В первой строке каждого описания содержится количество названных городов $$$m_i$$$ ($$$1 \le m_i \le 10^5$$$), а далее $$$m_i$$$ строк с названиями городов. Напомним, что в каждой партии число городов было чётным.
Название любого города содержит только латинские буквы, причём первая буква всегда заглавная, а остальные — строчные. Гарантируется, что название содержит хотя бы две буквы. Суммарная длина всех названий не превосходит $$$2 \cdot 10^5$$$ символов.
Для каждой игры в отдельной строке выведите ответ на задачу: название города, которым папа мог бы сделать ход, или «unknown» (без кавычек), если в предыдущих играх подходящего города не было.
$$$$$$\begin{array}{|c|c|c|c|c|} \hline \text { Подзадача } & \text { Баллы } & \text { Ограничения } & \text { Оценка } & \text { Необходимые подзадачи } \\ \hline 0 & 0 & \text { Тесты из условия } & \text { подзадача } & \\ \hline 1 & 20 & n = 2, \text{суммарная длина слов} \le 500 & \text { подзадача } & \\ \hline 2 & 40 & N \le 1000, \text{суммарная длина слов} \le 10^4 & \text { подзадача } & 1 \\ \hline 3 & 40 & \text { Без дополнительных ограничений } & \text { подзадача } & 1,2 \\ \hline \end{array}$$$$$$
3 4 Samara Aramavir Rome Erevan 2 Rostov Vilnius 4 Anapa Aramavir Riga Ankara
unknown Samara unknown
Саша принимает зачет по алгоритмам и любит задавать вопросы вида «что изменится в решении, если...». Это требует от студентов хорошего уровня понимания решения задачи. Саша хочет определить какой уровень понимания задачи взять за критерий зачета. У неё есть данные о понимании каждой задачи тестового студента Васи: для решения каждой задачи $$$i$$$, некоторая величина $$$u_i$$$, численно характеризующую его понимание этого решения (чем эта величина больше, тем лучше он понимает решение). Саша хочет подобрать такое $$$A$$$, что все объяснения уровня $$$u_i \ge A$$$ она примет, а для всех значений $$$u_i \lt A$$$ — объяснение не зачтет. Объяснять задачи нужно по порядку, начиная с первой. Кроме того, если Саша не принимает $$$k$$$ подряд идущих объяснений студента, то слушать объяснение следующей задачи она не будет. Помогите Саше подобрать такое максимальное $$$A$$$, при котором тестовый студент Вася получит зачет.
Студент получает зачет если смог рассказать решение всех $$$n$$$ задач с учетом всех требований экзаменатора.
В первой строке содержатся целые числа $$$n$$$ и $$$k$$$ $$$(1 \le n \le 10^5, \, 1 \le k \le n)$$$ — количество решений задач и количество неудачных объяснений подряд, после которого объяснение следующей задачи невозможно.
Во второй строке содержатся целые числа $$$u_1, u_2, \ldots, u_n$$$ $$$(1 \le u_i \le 10^5, \, i = 1, 2, \ldots, n)$$$ — показатель понимания Василием решений.
В первой строке выведите целое число — максимальное значение понимания для критерия зачета.
Если Вася сможет сдать зачет при любом сколь угодно большом критерии $$$A$$$, то выведите в качестве ответа $$$100000$$$.
$$$$$$\begin{array}{|c|c|c|c|c|} \hline \text { Подзадача } & \text { Баллы } & \text { Ограничения } & \text { Оценка } & \text { Необходимые подзадачи } \\ \hline 0 & 0 & \text { Тесты из условия } & \text { подзадача } & \\ \hline 1 & 25 & n, k \le 10, u_i \le 100 & \text { подзадача } & \\ \hline 2 & 20 & n, k \le 1000, u_i \le 100 & \text { подзадача } & 1 \\ \hline 3 & 55 & \text{ Без дополнительных ограничений } & \text { подзадача } & 1, 2 \\ \hline \end{array}$$$$$$
10 3
8 2 2 6 1 3 7 2 7 2
6
2 2
8 10
100000
Во время карантина Саша почти всё время сидела дома и заметила, что стала слишком мало двигаться. Чтобы контролировать свою активность, она купила фитнес-трекер и теперь каждый вечер смотрит, сколько шагов нашагала за день.
Однако решение одной проблемы сразу повлекло за собой другую: дело в том, что Саше нравятся далеко не все числа, так что в некоторые вечера она бывает не довольна результатом за день, даже если он был достаточно продуктивным. А именно, из всех натуральных чисел Саше нравятся только простые числа и степени двойки (т.к. остальные числа недостаточно математичные).
Но и для этой проблемы у Саши есть решение: теперь она смотрит показания трекера за некоторое время до сна, а потом совершает променад по квартире, пока число шагов не становится математичным.
Разумеется, Саша не помнит наизусть все математичные числа, так что просит вас помочь ей находить наименьшее подходящее математичное число.
В первой строке дано одно целое число $$$n$$$ ($$$1 \le n \le 10^5$$$) — число дней, в которые Саша носила фитнес-трекер.
Во второй строке даны $$$n$$$ целых чисел $$$a_i$$$ ($$$0 \le a_i \le 10^7$$$) — вечерние показания трекера в течение $$$n$$$ дней.
Выведите $$$n$$$ чисел: для каждого $$$a_i$$$ ближайшее математичное число, не меньшее его.
$$$$$$\begin{array}{|c|c|c|c|c|} \hline \text { Подзадача } & \text { Баллы } & \text { Ограничения } & \text { Оценка } & \text { Необходимые подзадачи } \\ \hline 0 & 0 & \text { Тесты из условия } & \text { подзадача } & \\ \hline 1 & 25 & n \le 1000, a_i \le 1000 & \text { подзадача } & \\ \hline 2 & 17 & n \le 1000 & \text { подзадача } & 1 \\ \hline 3 & 17 & a_i \le 1000 & \text { подзадача } & 1 \\ \hline 4 & 41 & \text{ Без дополнительных ограничений } & \text { подзадача } & 1, 2, 3 \\ \hline \end{array}$$$$$$
5 2020 1023 0 101 10000
2027 1024 1 101 10007
Как и Никита, Данила получил письма с кучей домашек. Разумеется, он тут же составил из них список и собрался выполнять в том порядке, в котором они записаны. Однако довольно быстро выяснилось, что далеко не все дела можно начать тогда, когда Данила это запланировал. Так что план придётся менять.
Для начала Данила разделил все домашки на подзадачи, выполнение каждой из которых займёт у него занимать одну (условную) единицу времени. Далее, для каждой подзадачи он определил день $$$s_j$$$, не раньше которого её можно начать выполнять, и день $$$f_j$$$, не позже которого её нужно закончить. Если в некоторый день Данил приступит к какой-либо подзадаче, то обязательно закончит её в этот же день.
Все домашки Данил хочет успеть выполнить за ближайшие $$$m$$$ дней. Также он хочет, чтобы подзадачи распределилсь достаточно равномерно, т.е. максимальное количество подзадач, которые он будет выполнять в течение одного дня, было минимально возможным.
Ваша задача — составить такой план распределения подзадач по дням.
В первой строке содержатся целые числа $$$n$$$ и $$$m$$$ $$$(1 \le n, \, m \le 3 \cdot 10^5)$$$ — число подзадач и число дней, за которые эти подзадачи нужно сделать.
В каждой из следующих $$$n$$$ строк содержится по два целых числа $$$s_j$$$ и $$$f_j$$$ $$$(1 \le s_j \le f_j \le m)$$$ — ограничения для $$$j$$$-й подзадачи.
В первой строке выведите целое число — минимально возможное максимальное число подзадач, которое придётся выполнить Даниле в течение одного дня.
В каждой из следующих $$$m$$$ строк выведите сначала число подзадач, которые Данил выполнит в этот день, а затем — номера этих подзадач.
Если существует несколько вариантов ответа, выведите любой.
$$$$$$\begin{array}{|c|c|c|c|c|} \hline \text { Подзадача } & \text { Баллы } & \text { Ограничения } & \text { Оценка } & \text { Необходимые подзадачи } \\ \hline 0 & 0 & \text { Тесты из условия } & \text { подзадача } & \\ \hline 1 & 27 & n, m \le 100 & \text { подзадача } & \\ \hline 2 & 35 & s_i, f_i \le 1000 & \text { подзадача } & 1 \\ \hline 3 & 38 & \text{ Без дополнительных ограничений } & \text { подзадача } & 1, 2 \\ \hline \end{array}$$$$$$
12 7
2 5
1 3
6 7
3 6
2 2
1 7
4 5
7 7
5 7
4 6
2 5
2 6
2
1 2
2 5 1
2 11 4
2 7 10
2 12 9
1 3
2 6 8
Макс и Костя работают в Яндексе и снимают квартиру недалеко от офиса. В этом же доме снимают квартиры многие их коллеги (потому что могут).
К сожалению, с марта ребятам приходится работать из дома, так что они не могут обедать в столовой Яндекса. Готовить ребята не умеют, так что постоянно заказывают еду в разных службах доставки. Так же поступают и их многочисленные соседи-коллеги.
Вчера Костя заболел, так что сегодня он не работает, а весь день сидит на подоконнике и грустно смотрит на улицу. Чтобы как-то занять себя, он следит за тем, какие доставщики еды подъезжают к его дому. За день к дому подъехало $$$n$$$ доставщиков, про каждого из которых Костя записал его компанию $$$a_i$$$ (им он присвоил номера от 1 до $$$10^9$$$).
Так как Костя — исследователь, он не может дать пропасть этому массиву данных. Для этого он хочет извлечь из него какую-нибудь полезную (или не очень) информацию. Например, какими службами доставки пользуются все его коллеги. Костя собирается выяснить это следующим образом: для каждого своего сослуживца он знает период его бодрствования, так что может выяснить, каких доставщиков он (чисто гипотетически) мог вызывать. Для $$$j$$$-го коллеги это были доставщики с $$$l_j$$$-го по $$$r_j$$$-го. Тогда для каждого коллеги Костя может определить самую вероятную службу доставки — ту, курьеров которой было больше всего в период его бодрствования.
Во время болезни Косте нельзя пользоваться ноутбуком, поэтому он просит вас закончить его исследование: для каждого живущего в доме сотрудника Яндекса определить самую вероятную для него службу доставки.
В первой строке дано одно целое число $$$n$$$ ($$$1 \le n \le 10^5$$$) — число доставшиков, увиденных Костей за день.
Во второй строке даны $$$n$$$ целых чисел $$$a_i$$$ ($$$1 \le a_i \le 10^9$$$) — номера службы доставки $$$i$$$-го доставщика.
В третьей строке дано одно целое число $$$q$$$ ($$$1 \le q \le 10^5$$$) — количество коллег Кости.
В следующих $$$q$$$ строках дано по два целых числа $$$l_j, r_j$$$ ($$$1 \le l_j \le r_j \le n$$$) — отрезок доставщиков, попадающих в период бодрствования $$$j$$$-го коллеги Кости.
Выведите $$$q$$$ целых чисел — для каждого яндексоида номер самой вероятной для него службы доставки. Если ответов несколько, выведите любой.
$$$$$$\begin{array}{|c|c|c|c|c|} \hline \text { Подзадача } & \text { Баллы } & \text { Ограничения } & \text { Оценка } & \text { Необходимые подзадачи } \\ \hline 0 & 0 & \text { Тесты из условия } & \text { подзадача } & \\ \hline 1 & 13 & n, q \le 100, a_i \le 100 & \text { подзадача } & \\ \hline 2 & 24 & n, q \le 10\,000, a_i \le 100 & \text { подзадача } & 1 \\ \hline 3 & 21 & n, q \le 10\,000, a_i \le 10\,000 & \text { подзадача } & 1, 2 \\ \hline 4 & 42 & \text{ Без дополнительных ограничений } & { потестовая } & 1, 2, 3 \\ \hline \end{array}$$$$$$
5 2 4 2 4 5 3 1 3 3 4 1 5
2 2 4