Портал обучения информатике. Подготовка к ЕГЭ, ОГЭ, олимпиадам

Бункеры#39676

Петя и Вася с упоением играют в шпионов. Сегодня они планируют, где будут
расположены их секретные бункеры и штаб-квартира.

Пока Петя и Вася решили, что им понадобится ровно n бункеров, которые для секретности будут пронумерованы числами от 1 до n.
Некоторые из них будут соединены двусторонними тоннелями, причем для надежности и секретности по тоннелям можно будет попасть из любого бункера в любой единственным образом.
Петя и Вася даже решили, какие из бункеров будут соединены тоннелями, но выбрать, какой из них будет штаб-квартирой, они не могут.
Мальчики хотят выбрать ее и разделить оставшиеся бункеры между собой таким образом, чтобы им досталось поровну бункеров к штаб-квартире вело бы ровно два тоннеля: один от бункера, принадлежащего Васе, другой - от бункера, принадлежащего Пете.

Уставший Петя пошел к себе домой, а утром Вася показал ему план, на котором бункеры были обозначены точками, а тоннели отрезками.
Кроме того, Вася выбрал штаб-квартиру таким образом, что нарисованный им план был симметричен относительно прямой, проходящей через точку, которая соответствовала штаб-квартире.

Хотя Петя почти сразу показал Васе, что тот ошибся и не нарисовал половину бункеров, ему стало интересно, можно ли выбрать штаб-квартиру и нарисовать такой симметричный план.

Входные данные:
В первой строке входного файла находится одно целое число n (1 <= n <= 10⁵) - количество бункеров.
В следующих n - 1 строках находится по два целых числа u_i и v_i (1 <= u_i, v_i <= n, u_i ≠ v_i) - номера бункеров, которые соединяет i-ый тоннель.
Гарантируется, что между любыми двумя бункерами существует единственный путь.

Выходные данные:
В выходной файл выведите "YES", если можно выбрать штаб-квартиру и нарисовать такой план, или "NO" если это невозможно.

Примеры:

Входные данные	Выходные данные
2 1 2	NO
3 1 2 2 3	YES

Деревья Хеш

✓ 1✗ 61 000средняяВойти и решать

Хэш двойной строки#39669

Вам дано t запросов, в каждом из которых вам дана строка s, состоящая из строчных латинских букв, число p и число mod.
Для каждого запроса вычислите полиномиальный хэш с основанием p по модулю mod от строки, являющейся строкой s, где каждая буква продублирована. То есть, если s = "isaac", то нужно посчитать хэш от строки "iissaaaacc".

Входные данные:
В первой строке дается число t - количество запросов.
Далее идет t строк, в каждой из которых через пробел даны s (1 <= |s| <= 20), p (1 <= p <= 10⁵) и mod (1 <= mod <= 10⁸).

Выходные данные:
Выведите ответы на запросы, каждый в отдельной строке.

Пример:

Входные данные	Выходные данные
2 isaac 12345 87654321 newton 54321 12345678	8829000 9632318

Вывод формулы Хеш

✓ 13✗ 27800средняяВойти и решать

Подпоследовательность с K числами#39528

Дана последовательность из N чисел. Рассматриваются все её непрерывные подпоследовательности, которые содержат ровно K отрицательных чисел, заканчивающихся цифрой m. Найдите среди них подпоследовательность с максимальной суммой. Программа должна вывести одно число – максимальную сумму элементов такой подпоследовательности. Гарантируется, что в исходной последовательности существует хотя бы K отрицательных чисел, заканчивающихся цифрой m.

Входные данные
В первой строке программа получается три числа: количество чисел в последовательности N (100 <= N <= 5000000), натуральное число K и целое число m (0 <= m <= 9). В каждой из следующих N строк записано одно целое число, не превышающее по модулю 10000. Гарантируется, что сумма любой подпоследовательности исходной последовательности не превышает по модулю 10⁹.

Выходные данные
Выведите на экран ответ на задачу.

Примеры

№	Входные данные	Выходные данные	Пояснение
1	8 2 3 6 -3 -2 4 -1 -13 8 13	12	Нужные нам числа -3 и -13. Вся исходная последовательность даст максимальную сумму элементов.

Алгоритмы обработки Префиксные суммы(минимумы, ...)

✓ 21✗ 1381 000средняяВойти и решать

Модифицированное демо - 2022#39481

Дана последовательность из N натуральных чисел. Рассматриваются все её непрерывные подпоследовательности, такие что сумма элементов каждой из них кратна K. Найдите среди них подпоследовательность с максимальной суммой, определите её длину. Если таких подпоследовательностей найдено несколько, в ответе укажите количество элементов самой короткой из них.

Входные данные
В первой строке записаны натуральные числа N (1 <= N <= 10⁸) и K (1 <= K <= 100). Каждая из следующих N строк содержит одно натуральное число, не превышающих 10000.

Выходные данные
Выведите на экран одно число - количество элементов самой короткой подпоследовательности с максимальной суммой элементов кратной К.

Примеры

№	Входные данные	Выходные данные
1	7 43 21 13 9 19 17 26 95	2

В этом наборе можно выбрать последовательности 21+13+9 (сумма 43) и 17+26 (сумма 43). Самая короткая из них, 17 + 26, имеет длину 2. Для указанных программа должна вывести число 2.

Остатки Префиксные суммы(минимумы, ...)

✓ 31✗ 1851 000средняяВойти и решать

Переключение между окнами#38849

Когда пользователь работает в операционной системе Windows, у него часто запущено несколько приложений. Каждое из приложений работает в отдельном окне. Для переключения между окнами используется комбинация клавиш «Alt+Tab». Эта комбинация делает активным окно, в котором пользователь работал перед тем, как перейти в текущее активное окно.

Чтобы переключиться в другое окно, можно нажать клавишу «Alt» и затем, не отпуская ее, несколько раз нажать клавишу «Tab». Чтобы понять, какое окно станет активным после этого, воспользуемся следующей моделью. Пусть запущено n приложений. Приложения в операционной системе организованы в виде списка и упорядочены по убыванию времени последней активности. То есть приложение, окно которого является активным в настоящий момент – первое в списке, приложение, окно которого было активно перед этим – второе, и т. д.

Если нажать клавишу «Alt» и затем, не отпуская ее, нажать клавишу «Tab» k раз, то активным станет окно приложения, которое находится на (k mod n) + 1-м месте в списке. Здесь a mod b означает остаток от деления a на b. Иными словами, операционная система рассматривает список как циклический, переходя после последнего элемента списка к первому.

При запуске нового приложения оно добавляется в начало списка.

Задана последовательность действий пользователя, где каждое действие – либо запуск приложения, либо переключение между окнами. Выведите список имен приложений в том порядке, в котором с ними работал пользователь.

Входные данные
В первой строке вводится целое число n – количество действий пользователя ( 1 ≤ n ≤ 1000). Следующие n строк содержат описание действий пользователя.

Запуск приложения описывается строкой «Run <имя приложения»>. Здесь «<имя приложения»> – строка из не более чем 100 латинских букв, цифр и пробелов. Она отделена от слова «Run» ровно одним пробелом. Все имена приложений различны. Большие и маленькие буквы считаются различными.

Переключение между приложениями описывается строкой «Alt+Tab+...+Tab», здесь подстрока «+Tab» повторена в точности столько раз, сколько раз пользователь нажал клавишу «Tab», не отпуская клавишу «Alt». Это количество не превышает 100.

Первая команда во входных данных – всегда команда «Run».

Выходные данные
Выведите n строк – последовательность имен приложений, с которыми работал пользователь в порядке, в котором их окна становились активными.

Примеры

№	Входные данные	Выходные данные
1	6 Run Mozilla Firefox Run Free Pascal Alt+Tab Run Miranda IM Alt+Tab+Tab Alt+Tab+Tab+Tab	Mozilla Firefox Free Pascal Mozilla Firefox Miranda IM Free Pascal Free Pascal

Задачи на моделирование Список

✓ 68✗ 178900средняяВойти и решать

Джерримендеринг#38777

Джерримендеринг — разделение территории на избирательные округа неестественным образом с целью искусственного изменения соотношения политических сил в них и, как следствие, в целом на территории проведения выборов. Например, при необходимости обеспечить победу на территории партии X (если от одного избирательного округа избирается один кандидат или один выборщик), нужно всех противников X сосредоточить по округам, где X не сможет выиграть, а всех сторонников X распределить так, чтобы они обеспечивали уверенную победу с небольшим перевесом в нужных округах. Например, в тесте из условия всего за X голосует 10 человек, а против X голосует 15 человек, но, благодаря специальному разделению по округам, X выигрывает в двух избирательных округах из трёх.
В этой задаче избирательная территория представляет собой улицу, на которой в ряд расположены N домов. В i-м доме проживает ai человек, и все они голосуют одинаково: либо за партию X, либо за другую партию. Улицу необходимо разбить на три избирательных округа, от каждого избирательного округа будет избираться один кандидат, и необходимо произвести такую нарезку улицы на три избирательных округа, чтобы минимум в двух округах из трёх выиграл кандидат от партии X. Кандидат от партии X выигрывает, если за него голосует более половины избирателей, проживающих в домах данного избирательного округа. Но чтобы вас не заподозрили в джерримендеринге, необходимо, чтобы каждый избирательный округ представлял собой непрерывный отрезок из номеров домов, то есть сначала вдоль по улице идут дома первого избирательного округа, затем — второго, затем — третьего. Каждый избирательный округ должен содержать как минимум один дом.

Входные данные
Первая строка входных данных содержит целое число N (3 <= N <= 10⁵ ) — количество домов на улице. Следующие N строк содержат по одному целому числу ai (0 < |ai | <= 10⁴ ). Если ai > 0, то в i-м доме проживает ai избирателей, голосующих за кандидата от партии X. Если ai < 0, то в i-м доме проживает |ai | избирателей, голосующих против кандидата от партии X.

Выходные данные
Если возможно разделить N домов на три округа так, что минимум в двух округах выигрывает кандидат от партии X, программа должна вывести в одной строке три целых положительных числа N1, N2, N3, N1 + N2 + N3 = N, соответствующих количеству домов в первом, втором и третьем избирательном округе от начала улицы. При таком разбиении минимум в двух округах из трёх должен выигрывать кандидат от партии X. Если возможно несколько таких разбиений, необходимо вывести любое из них.
Если искомое разбиение не существует, программа должна вывести одно число 0

Примеры

№	Входные данные	Выходные данные	Пояснение
1	7 -3 -5 3 -4 2 5 -3	4 1 2	На улице расположены 7 домов, избиратели в них распределены так: (−3, −5, 3, −4, 2, 5, −3). Правильный ответ: 4, 1, 2. При таком разбиении в первом округе оказываются 4 дома: (−3, −5, 3, −4). В этом округе за X голосует 3 избирателя, против — 12 избирателей и X разгромно проигрывает. В следующем округе один дом, в котором 2 избирателя голосуют за X, в этом округе X выиграет. В третьем округе два дома: (5, −3), и в этом округе X тоже выиграет. Итого X выигрывает в двух округах.

Префиксные суммы(минимумы, ...)реализация

✓ 14✗ 891 100средняяВойти и решать

Контейнеры#38599

На складе хранятся контейнеры с товарами N различных видов. Все контейнеры составлены в N стопок. В каждой стопке могут находиться контейнеры с товарами любых видов (стопка может быть изначально пустой).

Автопогрузчик может взять верхний контейнер из любой стопки и поставить его сверху в любую стопку. Необходимо расставить все контейнеры с товаром первого вида в первую стопку, второго вида – во вторую стопку и т.д.

Программа должна вывести последовательность действий автопогрузчика или сообщение о том, что задача решения не имеет.

Входные данные

В первой строке входных данных записано одно натуральное число N, не превосходящее 500. В следующих N строках описаны стопки контейнеров: сначала записано число k_i – количество контейнеров в стопке, а затем k_i чисел – виды товара в контейнерах в данной стопке, снизу вверх. В каждой стопке вначале не более 500 контейнеров (в процессе переноса контейнеров это ограничение может быть нарушено).

Выходные данные

Программа должна вывести описание действий автопогрузчика: для каждого действия напечатать два числа – из какой стопки брать контейнер и в какую стопку класть. (Обратите внимание, что минимизировать количество операций автопогрузчика не требуется.) Если задача не имеет решения, необходимо вывести одно число 0. Если контейнеры изначально правильно размещены по стопкам, то выводить ничего не нужно.

Примеры

№	Входные данные	Выходные данные	Пояснение
1	3 4 1 2 3 2 0 0	1 2 1 3 1 2	Изначально в первой стопке лежат четыре контейнера – снизу контейнер с товаром первого вида, над ним – с товаром второго вида, над ним третьего, и сверху еще один контейнер с товаром второго вида. Вторая и третья стопки – пусты.

Стек

✓ 62✗ 2201 000средняяВойти и решать

Практический тест#38589

У нас есть сетка с H строками и W столбцами. Квадрат в i-й строке и j-м столбце будет называться Square(i, j). Целые числа от 1 до H·W записаны по всей сетке, а целое число, записанное в Square(i, j), равно A_i,j.
Вы - волшебник (волшебница), и можете телепортировать фигуру, помещенную на Square(i, j) в Square(x, y), потратив \(|x-i|+|y-j|\) маджиков (магических монет).
Теперь вам нужно пройти Q практических тестов на свои способности как волшебника (волшебницы). I-е испытание будет проводиться следующим образом:
- первоначально фигура располагается в квадрате, где записано целое число L_i;
- пусть x будет целым числом, записанным в квадрате, занятом фигурой. Неоднократно переместите фигуру в квадрат, где написано целое число x+D, пока x не станет равен R_i. Тест заканчивается, когда x = R_i .
Гарантируется, что R_i- L_i делится на D.
Для каждого теста найдите сумму маджиков, израсходованных во время этого теста.

Входные данные
В первой строке заданы три целых числа: H, W и D (\(1\leq H,W \leq 300\), \(1 \leq D \leq H \cdot W\)).
В следующих H строках записано по W чисел A_i,j(\(1 \leq A_{i,j} \leq H \cdot W\), \(A_{i,j} \neq A_{x,y} ((i,j) \neq (x,y))\).
В следующей строке записано целое число Q (\(1 \leq Q \leq 10^5\)).
В последних Q строках записано по 2 целых числа: L_i и R_i (\(1 \leq L_i \leq R_i \leq H \cdot W\)), \((R_i-L_i)\) кратно D.

Выходные данные
Для каждого теста выведите сумму маджиков, израсходованных во время этого теста. Вывод должен быть в порядке проведения тестов.

Примеры

№	Входные данные	Выходные данные	Пояснения
1	3 3 2 1 4 3 2 5 7 8 9 6 1 4 8	5	- 4 записано Square (1,2). - 6 записано в Square (3,3). - 8 записано in Square (3,1). Таким образом, сумма магических очков, израсходованных во время одного теста, составляет: \((\|3-1\|+\|3-2\|)+(\|3-3\|+\|1-3\|)=5\).
2	4 2 3 3 7 1 4 5 2 6 8 2 2 2 2 2	0 0	Обратите внимание, что может быть тест, в котором фигура вообще не перемещается, и может быть несколько идентичных тестов.
3	5 5 4 13 25 7 15 17 16 22 20 2 9 14 11 12 1 19 10 6 23 8 18 3 21 5 24 4 3 13 13 2 10 13 13	0 5 0

Динамическое программирование: один параметр Массивы Префиксные суммы(минимумы, ...)

✓ 5✗ 151 100средняяВойти и решать

Коллайдер#38476

Физики проводят эксперимент для исследования частиц трёх типов: x, y и z. Они запускают в коллайдер пронумерованный ряд из n частиц. Во время эксперимента происходит воздействие на одну конкретную частицу, после чего частица исчезает с i-ого места ряда и моментально появляется на месте j. После её исчезновения номера частиц, стоящих правее, уменьшаются на 1, а после появления, номера частиц, стоящих правее, увеличиваются на 1. После определенного числа воздействий физики интересуются какая частица стоит на месте k. Напишите программу, которая поможет физикам.

Входные данные
В первой строке файла два целых числа: n – количество частиц и m — общее количество воздействий и вопросов (1 ≤ n ≤ 1000000, 1 ≤ m ≤ 15000). Во второй строке — последовательность из символов x, y и z длиной n. На каждой из следующих m строк (1 ≤ m ≤ 15000) описано воздействие или вопрос. Строка, в которой описано воздействие, начинается символом a и после пробела дается два целых числа из интервала [1; n]. Первое из них показывает начальное, а второе - конечное местоположение частицы во время воздействия. Строка, в которой описан вопрос, начинается символом q и после пробела дается одно целое число из интервала [1; n]. Оно указывает позицию, которая интересует физиков.

Выходные данные
Выведите столько строк, сколько вопросов во входном файле. В строке номер i надо записать ответ на вопрос i — название соответствующей частицы x, y или z.

Пояснения к примеру
Последовательность после первого воздействия – xxyyzxxzxzyyzyx, последовательность после второго воздействия – xxyxyzxxzxzyyzy, последовательность после третьего воздействия – xyxyxyzxxzxzyzy,

Примеры

№	Входные данные	Выходные данные
1	15 6 xzxyyzxxzxyyzyx a 2 10 a 15 4 q 3 a 12 2 q 14 q 2	y z y

Двоичное дерево поиска Задачи на моделирование

✓ 1✗ 14900средняяВойти и решать

Взвешивание камней#38473

Джек нашел N камней и упорядочил их в порядке возрастания их массы. Массы всех камней различны. Самый легкий камень получил номер 1, следующий ≤ 2 и так далее, самый тяжелый получил номер N.

У Джека есть чашечные весы и он решил положить все камни на них в каком-то порядке. Известен порядок, в котором он будет класть камни, и какой камень на какую чашу попадет.

Ваша задача — определить состояние весов после добавления каждого камня. Точные массы камней не известны — даются только их номера.

Входные данные
Первая строка содержит целое число N (1 N ≤ 100000).

Каждая из следующих N строк содержит по два целых числа: R (1 ≤ R ≤ N) и S (1 ≤ S ≤ 2). R - номер камня, который будет положен на чашу S. Все R будут различны.

Выходные данные
Выведите N строк - по одной для каждого камня. Если после добавления соответствующего камня чаша 1 тяжелее, выведите “<”. Если сторона 2 тяжелее, выведите “>”. Если невозможно определить, в каком состоянии будут весы, выведите “?”.

Примеры

№	Входные данные	Выходные данные
1	5 1 2 3 1 2 1 4 2 5 1	< > > ? >

Алгоритмы сортировки Дерево отрезков, RSQ, RMQ Жадный алгоритм

✓ 1✗ 121 100средняяВойти и решать

Шахматные баталии#38386

Ильдар и Ваня устали постоянно играть в шахматы, поэтому они придумали новую шахматную игру.

Игра происходит на шахматном поле размером 2n×2m. Это поле имеет 2n строк и 2m столбцов. Для удобства будем обозначать как (i, j) клетку поля, которая находится в i-й строке и j-м столбце. Клетки этого поля покрашены в черный и белый цвета шахматной раскраской. Более точно, клетка (i, j) имеет белый цвет, если i + j чётно, и чёрный цвет в противном случае.

Игра устроена следующим образом. Ильдар вырезает некоторые белые клетки поля. После этого он предлагает Ване попробовать решить следующую задачу: может ли он на не вырезанных белых клетках поля расставить nm шахматных королей так, что никакие два выставленных короля не бьют друг друга, то есть не стоят на клетках поля, соседних по стороне или углу.

Конечно, Ильдар планирует сделать игру интересной и выставить несколько непростых для Вани комбинаций вырезанных клеток. Для этого он попросил у вас помощи. Чтобы перед игрой понять, как лучше всего действовать, он хочет потренироваться. Для этого, он берёт пустое поле и хочет q раз либо вырезать какую-то белую клетку, либо вернуть на поле какую-то ранее вырезанную клетку. После каждого изменения он бы хотел знать, каким будет ответ на задачу для Вани.

Помогите Ильдару сделать игру интересной! Напишите программу, которая будет отвечать на его запросы.

Формат входных данных
В первой строке находится три целых числа n, m, q (1 ≤ n, m, q ≤ 200 000) — количество пар строк шахматной доски, количество пар столбцов шахматной доски и количество запросов.
Следующие q строк описывают запросы Ильдара. Каждая из этих строк содержит два целых числа i, j (1 ≤ i ≤ 2n, 1 ≤ j ≤ 2m, i+j четно). Если клетка (i, j) не вырезана, то Ильдар её вырезает, иначе он возвращает её обратно на поле.

Формат выходных данных
Выведите q строк. В i-й из этих строк выведите ответ на задачу для доски, полученной после i первых запросов Ильдара.
Выведите «YES» (без кавычек), если Ваня может так расставить шахматных королей на не вырезанные белые клетки поля, что никакие два короля не будут бить друг друга. Иначе выведете «NO» (без кавычек).

Примеры

№	Входные данные	Выходные данные
1	1 3 3 1 1 1 5 2 4	YES YES NO
2	3 2 10 4 2 6 4 1 3 4 2 6 4 2 2 2 4 1 3 4 4 3 1	YES YES NO NO YES YES NO YES YES NO

Замечание
В первом примере, после второго запроса будут вырезаны клетки (1, 1) и (1, 5). Тогда Ваня может поставить три короля на клетки (2, 2), (2, 4) и (2, 6).
После третьего запроса будут вырезаны клетки (1, 1), (1, 5) и (2, 4). Тогда остаётся всего три пустые клетки (2, 2), (1, 3) и (2, 6). Ваня не может поставить трех королей на эти клетки, потому что короли в клетках (2, 2) и (1, 3) бьют друг друга, так как эти клетки соседние по углу.

Дерево отрезков, RSQ, RMQ

✓ 2✗ 31 100средняяВойти и решать

Выбор цветов для букета#38384

Володя хочет красиво поздравить свою жену с годовщиной их свадьбы и собирается подарить ей букет из n цветов.

Придя в цветочный магазин, Володя обнаружил, что букет можно составлять из цветов m различных видов, причём количество цветов каждого вида не ограничено. Володя знает, что от первого цветка i-го вида в букете его супруга становится счастливее на a_i, а от каждого следующего цветка
такого вида она становится счастливее на b_i. То есть, если в букете x_i > 0 цветов вида i, то от цветов этого вида жена Володи становится счастливее на a_i + (x_i − 1) · b_i.

Как любой любящий муж, Володя хочет как можно сильнее порадовать свою супругу. Поэтому ему хочется знать, на какую максимальную величину может увеличиться её счастье от букета, набранного из доступных в магазине цветов.

Формат входных данных
В первой строке вводятся два целых числа n и m (1 ≤ n ≤ 10⁹ , 1 ≤ m ≤ 100 000) — требуемое
количество цветов в букете и количество доступных видов цветов.
Каждая из следующих m строк описывает i-й вид цветов и содержит два целых числа a_i и b_i (0 ≤ a_i , b_i ≤ 10⁹ ) — увеличение счастья от первого цветка i-го вида и увеличение счастья от каждого последующего цветка этого вида.

Формат выходных данных
В единственной строке выведите одно число — максимальное увеличение счастья, которое может получить жена Володи от букета из n цветов.

Примеры

№	Входные данные	Выходные данные
1	4 3 5 0 1 4 2 2	14
2	5 3 5 2 4 2 3 1	16

Бинарный поиск в массиве Префиксные суммы(минимумы, ...)

✓ 6✗ 331 000средняяВойти и решать

Волшебные грибы#38374

На планете Руук существует Большая Корпорация Маленьких Фей. Одним из видов деятельности, которым испокон веков занимаются ее сотрудницы, является посадка грядок с волшебными грибами. Каждый день, начиная с самого первого дня существования этой корпорации, феи создают одну новую грядку грибов. После этого с новой грядки два дня можно собирать споры, которыми размножаются эти грибы, а потом грядка будет поставлять уже только сам продукт — грибы.

Таким образом, если обозначить количество грибов, посаженных на грядке, созданной в день номер i, как c_i, то оно будет считаться по формуле c_i = c_i - 1 + c_i - 2. Так, в первый и второй дни было посажено по одному грибу, в третий — два, в четвертый — три, в пятый — пять и так далее.

Волшебные грибы являются самыми ценными сувенирами, которые путешественник может привезти с планеты Руук. Поэтому первым, что делает любой приезжий, становится поиск грядки с волшебными грибами. Однако, в последнее время все чаще стали появляться сообщения о поддельных волшебных грибах. Тщательное расследование показало, что это является следствием действий Маленькой Корпорации Больших Фей, которая сажает грядки с грибами, внешне не отличимыми, но далеко не такими ценными, как волшебные. Причем, создавая очередную грядку, эти феи сажают туда такое количество грибов, какое их соперницы никогда не сажали и не смогут посадить.

Казалось бы, после выяснения этого факта отличать волшебные грядки от поддельных стало просто. Но обе корпорации существуют достаточно давно, количество грядок и грибов на них давно превысило все разумные пределы. Вас попросили написать программу, по количеству грибов на грядке сообщающую, является ли эта грядка волшебной.

Входные данные

Первая строка входного файла содержит одно число N (1 ≤ N ≤ 1000000) — количество исследуемых грядок. Следующие n строк содержат по одному целому числу a_i — количества грибов на исследуемых грядках. Размер входного файла не превышает 1 Мб.

Выходные данные

Для каждого числа, данного во входном файле, выведите «Yes», если грядка с таким количеством грибов является волшебной, и «No» — если не является. Ответы разделяйте переводами строк.

Примеры

№	Входные данные	Выходные данные
1	8 1 2 3 4 5 6 7 8	Yes Yes Yes No Yes No No Yes

Хеш

✓ 4✗ 1301 100средняяВойти и решать

Выбор гурмана#38303

Гурман Яблочков работает редактором известного гастрономического издания. Он разъезжает по всему миру, дегустируя новые изыски именитых шеф-поваров самых фешенебельных ресторанов высокой кухни. У Яблочкова есть свой фирменный способ ревью: в каждом заведении Яблочков заказывает два набора блюд в разные дни. Все заказанные блюда разные, так как Яблочков не любит есть одно и то же. Для каждой пары блюд из разных наборов он точно помнит, какое из них лучше по его ощущениям, или что они одинаковы по вкусовым качествам. Затем гурман оценивает каждое блюдо положительным целым числом.

Однажды, во время очередной ревизии, ресторан кельтской средневековой кухни «Пуассон», подающий суп из каштанов с пихтой, теплый содовый хлеб, пряный лимонный пирог и другую народную еду, очень приятно удивил гурмана своим разнообразным меню, и эксперт заказал слишком много. Поэтому ему нужна помощь в оценке блюд.

Гурман в первый день дегустировал набор из n блюд, во второй день набор из m блюд. Он составил таблицу ощущений a размером nm, в которой описал свои впечатления. Если по мнению эксперта блюдо i из первого набора лучше блюда j из второго набора, то a_ij равно « > », в противоположном случае a_ij равно « < ». Блюда также могут быть равны по уровню, тогда a_ij равно « = ».

Теперь Яблочков хочет, чтобы вы помогли ему оценить каждое блюдо в наборах целым положительным числом. Так как Яблочков очень строгий дегустатор, то постарается оценить блюда так, чтобы максимальная из оценок была как можно меньше. В то же время Яблочков очень справедливый, поэтому никогда не оценивает блюда так, чтобы это шло вразрез с его ощущениями. Другими словами, если a_ij равно « < », то оценка блюда i из первого набора должна быть меньше оценки блюда j из второго набора, если a_ij равно « > », то должна быть больше, а если a_ij равно « = », то должна совпадать.

Помогите Яблочкову выставить оценки каждому блюду из обоих наборов так, чтобы это согласовывалось с его ощущениями, или определите, что это невозможно.

Входные данные
В первой строке заданы два целых числа n и m (1 ≤ n, m ≤ 1000 ) — количества блюд в каждый из двух дней.

Каждая из следующих n строк содержит строку из m символов. j-й символ в i-й строке задаёт значение aij. Все строки состоят только из символов « < », « > » и « = ».

Выходные данные
В первой строке выведите « Yes » (без кавычек), если можно сделать корректную оценку всем блюдам и « No » (без кавычек), если иначе.

В случае, если сделать корректную оценку можно, во второй строке выведите n целых чисел — оценки блюд первого набора, а в третьей строке m целых чисел — оценки блюд второго набора.

Примеры

№	Входные данные	Выходные данные	Пояснения
1	3 4 >>>> >>>> >>>>	Yes 2 2 2 1 1 1 1	Все блюда первого дня лучше всех блюд второго дня. Значит, самой высокой оценкой будет 2 для всех блюд первого дня.
2	3 3 >>> <<< >>>	Yes 3 1 3 2 2 2
3	3 2 == =< ==	No	Таблица противоречива: нет ни одного набора оценок, который удовлетворял бы ей.

Динамическое программирование на графах Обход в глубину Система непересекающихся множеств

✓ 4✗ 71 000средняяВойти и решать

Комфортабельные коровы#38142

Пастбище Фермера Юрика может рассматриваться как огромная 2D-решётка ячеек (шахматная доска). Изначально пастбище пустое.

Фермер Юрик добавит N (\(1<=N<=10^5\)) коров на пастбище одну за другой. i-ая корова займёт ячейку (x_i,y_i), которая отличается от ячеек, занятых всеми другими коровами (\(0<=x_i,y_i<=1000\)).

Корова называется "комфортабельной", если она имеет ровно трёх соседей по горизонтали и вертикали. Комфортабельные коровы дают меньше молока, поэтому Фермер Юрик хочет добавлять коров пока нет комфортабельных (включая ту которую он добавит). Заметим, что добавляемые коровы не обязательно должны иметь координаты x и y в интервале \(0…1000\).

Для каждого i в интервале \(1…N\), выведите минимальное количество коров, которое он должен добавить, чтобы не осталось комфортабельных коров, если считать, что на пастбище находятся только коровы \(1…i\).

Входные данные
Первая строка содержит целое число N. Каждая из следующих N строк содержит по 2 разделённых пробелом целых числа (x, y), указывающих координаты ячейки с коровой.

Выходные данные
Минимальное количество коров, которое Фермер Юрик должен добавить, для каждого i в интервале \(1…N\), на отдельной строке.

Примеры

№	Входные данные	Выходные данные	Пояснение
1	9 0 1 1 0 1 1 1 2 2 1 2 2 3 1 3 2 4 1	0 0 0 1 0 0 1 2 4	Для i=4, Фермер Юрик должен добавить корову в позицию (2,1), чтобы сделать корову в позиции (1,1) некомфортабельной. Для i=9, лучшее что Фермер может сделать - добавить коров в позиции (2,0), (3,0), (2,−1), (2,3).

Очередь Разбор случаев

✓ 2✗ 101 100средняяВойти и решать

Организация коров фермера Джона#38133

Организация коров фермера Джона (UCFJ) направляет делегацию на Международную олимпиаду по овцеводству (IOI).
N коров участвуют в выборе делегации (1≤N≤2⋅10⁵). Они стоят в ряд, и корова i имеет породу b_i.

Делегация состоит из непрерывного интервала как минимум двух коров - то есть из коров l…r для целых l и r удовлетворяющих 1≤l<r≤N. две внешние коровы выбранного интервала называются "лидерами". Чтобы избежать конфликта между породами коров каждый лидер должен иметь породу отличающуюся от остальных коров делегации (лидеров и не лидеров).

Определите количество способов выбрать делегацию.

Входные данные:
Первая строка содержит N.
Вторая строка содержит N целых чисел b₁,b₂,…,b_N, каждое в интервале [1,N].

Выходные данные:
Количество возможных делегаций, на отдельной строке.

Примеры

№	Входные данные	Выходные данные	Пояснение
1	7 1 2 3 4 3 2 5	13	Каждая делегация соответствует одной из следующих пар лидеров: (1,2),(1,3),(1,4),(1,7),(2,3),(2,4),(3,4),(4,5),(4,6),(4,7),(5,6),(5,7),(6,7).

Двоичное дерево поиска

✓ 4✗ 111 000средняяВойти и решать

Свойства объектов - 1#37887

В хранилище Васи находится n объектов, пронумерованных от 1 до n, у каждого из которых есть некоторое количество свойств (возможно, ни одного). Каждое свойство представлено в виде натурального числа от 1 до 10⁹.
Проанализировав устройство своего хранилища, Вася решил, что оно должно поддерживать две операции:
- Удаление устаревшего свойства c. При удалении свойства, оно удаляется у всех объектов, которым принадлежит.
Если указанного свойства не существует, ничего делать не нужно.
- Найти количество оставшихся свойств у объекта с номером r.
Васе очень нужно реализовать эту функциональность, и он обратился к вам за помощью. Помогите ему - напишите программу, которая будет поддерживать обе операции, нужные Васе.

Формат входных данных
В первой строке входного файле содержится число n - количество объектов в хранилище Васи (1 <= n <= 10⁵). В i-й из следующих n строк содержится описание свойств объекта с номером i: сначала дано число ki - количество свойств у i-го объекта, а затем через пробел даны ki чисел pi,j - свойства i-го объекта (0 <= k_i <= 100, 1 <= p_i,j <= 10⁹).
Все объекты пронумерованы от 1 до n в порядке, представленном во входных данных. Гарантируется, что общее количество свойств у всех объектов не превосходит 10⁵. Также гарантируется, что для каждого i все pi,j различны.
В n + 2 строке содержится число q - количество запросов к хранилищу Васи (1 <= q <= 10⁵).
В j-й из следующих q строк содержится информация об j-м запросе:
- c, если из хранилища требуется удалить устаревшее свойство c (1 <= c <= 10⁹);
? r, если требуется найти количество оставшихся свойств у объекта с номером r.

Формат выходных данных
Для всех запросов на нахождение количества оставшихся свойств у объекта, в отдельных строках, в порядке их поступления для каждого запроса выведите это количество.

Ввод	Вывод
2 3 1 2 4 3 2 3 5 12 - 1 ? 1 ? 2 - 2 ? 1 ? 2 - 5 ? 1 ? 2 - 6 ? 1 ? 2	2 3 1 2 1 1 1 1

Замечание
Свойство 1 есть только у первого объекта, поэтому после его удаления у первого объекта остается 2 свойства, а у второго все еще 3.
Свойство 2 есть у обоих объектов, поэтому оно удаляется у обоих объектов, у первого объекта остается 1 свойство, а у второго - 2.
Свойство 5 есть только у второго объекта, поэтому после его удаления у обоих объектов остается 1 свойство.
Свойства 6 нет ни у одного объекта, поэтому его удаление не меняет количество свойств у объектов.

Задача на реализацию Хеш

✓ 8✗ 66800средняяВойти и решать

Исправляем XML#34978

Формат XML является распространенным способом обмена данными между различными программами. Недавно программист Иванов написал небольшую программу, которая сохраняет некоторую важную информацию в виде XML-строки.

XML-строка состоит из открывающих и закрывающих тегов.

Открывающий тег начинается с открывающей угловой скобки (<), за ней следует имя тега — непустая строка из строчных букв латинского алфавита, а затем закрывающая угловая скобка (>).
Примеры открывающих тегов: <a>, <dog>.

Закрывающий тег начинается с открывающей угловой скобки, за ней следует прямой слеш (/), затем имя тега — непустая строка из строчных букв латинского алфавита, а затем закрывающая угловая скобка.
Примеры закрывающихся тегов: </a>, </dog>.

XML-строка называется корректной, если она может быть получена по следующим правилам:

Пустая строка является корректной XML-строкой.
A и B — корректные XML-строки, то строка AB, получающаяся приписыванием строки B в конец строки A, также является корректной XML-строкой.
Если A — корректная XML-строка, то строка <X>A</X>, получающаяся приписыванием в начало A открывающегося тега, а в конец — закрывающегося с таким же именем, также является корректной XML-строкой. Здесь X — любая непустая строка из строчных букв латинского алфавита.

Например, представленные ниже строки:
<a></a>
<a><ab></ab><c></c></a>
<a></a><a></a><a></a>
являются корректными XML-строками, а такие строки как:
<a></b>
<a><b>
<a><b></a></b>
не являются корректными XML-строками.

Иванов отправил файл с сохраненной XML-строкой по электронной почте своему коллеге Петрову. Однако, к сожалению, файл повредился в процессе пересылки: ровно один символ в строке заменился на некоторый другой символ.
Требуется написать программу, которая по строке, которую получил Петров, восстановит исходную XML-строку, которую отправлял Иванов.

Входные данные: Входной файл содержит одну строку, которая заменой ровно одного символа может быть превращена в корректную XML-строку. Длина строки лежит в пределах от 7 до 1000, включительно. Строка содержит только строчные буквы латинского алфавита и символы «<» (ASCII код 60), «>»(ASCII код 62) и «/»(ASCII код 47).

Строка во входном файле заканчивается переводом строки.

Выходные данные: Выходной файл должен содержать корректную XML-строку, которая может быть получена из строки во входном файле заменой ровно одного символа на другой. Если вариантов ответа несколько, можно вывести любой.

Примеры

№	Входные данные	Выходные данные
1	<a></b>	<a></a>
2	<a><aa>	<a></a>
3	<a><>a>	<a></a>
4	<a/</a>	<a></a>

Стек

✓ 26✗ 1331 100средняяВойти и решать

Турнир#34778

В турнире участвуют N команд. Турнир проводится по олимпийской системе (команды играют на вылет, проигравшие команды выбывают из турнира, выигравшие проходят в следующий тур, ничьих не бывает). Число команд в этой задаче будет степенью двойки: N = 2 ^k .

Все команды пронумерованы числами от 1 до N. В первом туре играют команды с номерами 1 и 2, 3 и 4, 5 и 6 и т. д., всего играется N/2 матчей. По результатам этих матчей команды выходят во второй тур. Во втором туре играют победители первой и второй игры первого тура, победители третьей и четвёртой игры первого тура и т. д. Они выходят в третий тур. В третьем туре играют вместе победители первой и второй игры второго тура, победители третьей и четвёртой игры второго тура и т. д.

Вам даны результаты всех матчей. Определите номер команды, которая стала победителем турнира.
В первой строке входных данных записано число N – количество команд, участвовавших в турнире. Оно является степенью двойки и может принимать значения от 2⁰ = 1 до 2¹⁶ = 65536. Следующие N − 1 строк содержат результаты всех сыгранных матчей. Первые N/2 строк из них являются результатами матчей первого тура, затем идёт N/4 строк с результатами второго тура, N/8 строк с результатами третьего тура и т. д.

Результат каждого матча является одним из двух возможных чисел: 1 или 2. Число 1 означает, что в матче выиграла первая команда (номер которой меньше), число 2 означает, что в матче выиграла вторая команда (номер которой больше).
Программа должна вывести одно число – номер победившей в турнире команды.

Ввод	Вывод
8 1 2 2 1 2 1 1	4

Примечание к ответу
Далее нарисована схема турнира для примера из условия. В турнире участвовало 8 команд. Результаты матчей: 1, 2, 2, 1, 2, 1, 1.
В первом туре играли команды 1 и 2, 3 и 4, 5 и 6, 7 и 8. Результаты матчей первого тура: 1, 2, 2, 1, во второй тур вышли команды 1, 4, 6, 7.
Во втором туре играли команды 1 и 4, 6 и 7. Результаты матчей второго тура: 2, 1.
В третий тур вышли команды 4 и 6. В последнем, третьем, туре играют команды 4 и 6, результат матча: 1, поэтому победителем турнира является команда 4.

Задача на реализацию Задачи на моделирование Структуры данных

✓ 56✗ 51800средняяВойти и решать

Ася и котята#33481

Ася очень любит животных. Недавно она приобрела n котят, дала им числовые идентификаторы от 1 до n и поселила в вольере. Вольер представляет собой ряд из n ячеек, также пронумерованных от 1 до n. Cоседние ячейки разделены сетчатыми перегородками, всего в вольере n−1 перегородок. Изначально в каждой ячейке поселился ровно один котёнок с некоторым номером.

Наблюдая за котятами, Ася заметила, что они очень дружелюбны и некоторые пары живущих в соседних ячейках котят очень хотят играть друг с другом. Чтобы не лишать их этого удовольствия, Ася стала вынимать перегородки между соседними ячейками, делая их более крупными.

В i-й день Ася делала следующее.

Обращала внимание, что какие-то котята x_i и y_i, в i-й день живущие в соседних ячейках, хотят играть.
Удаляла перегородку между этими ячейками, превращая их в одну, в которой оказывались все котята из двух прежних ячеек.
Поскольку Ася не возвращала перегородки, через n−1 день вольер стал единой ячейкой, в которой обитали все котята. Будучи очень педантичной, Ася записывала в специальный журнал идентификаторы котят x_i и y_i для каждого из n−1 дней.

Вам в руки попал журнал с этой информацией, однако вам неизвестно, как котята были поселены в ячейки изначально. Найдите любое расселение котят по n исходным ячейкам, не противоречащее данным в журнале.

Входные данные
В первой строке задано целое число n (\(2 \leq n \leq 150000\)) — количество котят.

В следующих n−1 строках заданы пары целых чисел x_i , y_i ( \(1 \leq x_i, y_i, \leq n,x_i \neq y_i\) ) — идентификаторы котят, между ячейками которых была удалена перегородка в день i. Гарантируется, что котята xi и yi не находятся в одной ячейке по итогам предыдущих объединений ячеек.

Выходные данные
Выведите n различных целых чисел p_i (\(1 \leq p_i \leq n\)), где p_i — идентификатор котёнка, который изначально жил в ячейке с номером i. Если возможных вариантов ответа несколько, выведите любой из них.

Примечание
В ответе к примеру приведено одно из возможных изначальных расселений котят, существуют и другие варианты ответа. На изображении ниже показано, как происходило объединение ячеек для этого варианта исходного размещения котят. Обратите внимание, что при таком размещении котята, подружившиеся в каждый из дней согласно журналу Аси, находятся в соседних ячейках.

Ввод	Вывод
5 1 4 2 5 3 1 4 5	3 1 4 2 5

Система непересекающихся множеств

✓ 14✗ 491 000средняяВойти и решать