В компьютерной игре «Цивилизация-X» каждый игрок управляет империей, состоящей из нескольких городов. Некоторые города (как одного и того же игрока, так и разных игроков) могут быть соединены торговыми путями.
Основной задачей каждого игрока является захват городов других игроков. После того, как город захвачен, в нем начинаются беспорядки; на ликвидацию беспорядков в городе надо потратить некоторое количество золотых монет. Количество монет равно количеству городов, которые соединены с захваченным городом торговыми путями, и которые при этом принадлежат другим игрокам.
Обратите внимание, что между парой городов может быть несколько торговых путей, но все равно при расчете количества монет каждый город, соединенный с захваченным городом торговыми путями, учитывается только один раз.
Торговые пути двунаправленные, т.е. каждый путь учитывается при захвате любого из городов, которые соединены этим путем.
После захвата города все торговые пути сохраняются.
Например, если игрок A захватывает город, соединенный торговыми путями с семью городами, четыре из которых принадлежат игроку A, два — игроку B и один — игроку C, то игрок A должен будет потратить три монеты на ликвидацию беспорядков. Если после этого этот же город захватит игрок B, то на ликвидацию беспорядков он должен будет потратить 5 монет.
Чтобы победить в игре, надо захватить все города, которые есть в мире.
Будем считать, что игроки не строят новые города и не создают новые торговые пути. Рассмотрим некоторую конфигурацию городов и торговых путей. Ценой победы игрока назовем минимальное количество монет, которые ему придется потратить на ликвидацию беспорядков, если он хочет победить. Определите игрока, цена победы которого минимальна.
В первой строке входных данных находятся три числа $$$N$$$, $$$M$$$ и $$$K$$$ — количество городов, торговых путей и количество игроков ($$$1\leq N, K\leq 100\,000$$$; $$$0\leq M\leq 100\,000$$$).
Во второй строке находятся $$$N$$$ чисел от 1 до $$$K$$$, $$$i$$$-е из которых равно номеру игрока, которому изначально принадлежит $$$i$$$-й город.
Далее следуют $$$M$$$ строк, каждая из которых содержит два различных числа — номера городов, соединяемых очередным торговым путем.
Города и игроки нумеруются начиная с 1. Могут быть игроки, которым изначально не принадлежит ни один город.
Выведите в выходной файл два числа — номер игрока, цена победы которого минимальна, и его цену победы. Если таких игроков несколько, выведите игрока с наименьшим номером.
Подзадача 1, 30 баллов: $$$N, M, K\leq 20$$$.
Подзадача 2, 30 баллов: $$$N, M, K \leq 1000$$$.
Подзадача 3, 30 баллов: нет городов, соединенных более чем одним торговым путем.
Подзадача 4, 10 баллов: дополнительных ограничений нет.
Кроме того, в тестах общей стоимостью 30 баллов (распределенных по разным подзадачам) будет выполняться условие $$$K=2$$$.
4 5 3 2 2 3 1 1 2 1 4 3 4 2 3 3 2
2 1
Представим себе бесконечную аллею, которая идет вдоль оси $$$OX$$$ и начинается в точке $$$X=0$$$.
С каждой из сторон аллеи посажены деревья. С одной стороны деревья посажены в точках $$$A$$$, $$$A+B$$$, $$$A+2\cdot B$$$ и так далее, то есть в точках $$$A+N\cdot B$$$ для любого целого неотрицательного $$$N$$$. При этом $$$0 \leq A \lt B$$$. Аналогично, с другой стороны аллеи деревья посажены в точках $$$C$$$, $$$C+D$$$, $$$C+2\cdot D$$$ и так далее. При этом $$$0 \leq C \lt D$$$. Обратите внимание, что в некоторых точках может оказаться два дерева — по одному с каждой из сторон аллеи (см. пример 1).
Вася любит фотографировать деревья. Он хочет прогуляться по аллее и сфотографировать минимум $$$K$$$ деревьев. Однако, он может фотографировать дерево только если находится в одной точке с ним. Вася довольно ленив и хочет пройти вдоль аллеи наименьшее возможное расстояние. При этом он может начать движение в любой точке аллеи — он просто подъедет к ней на машине. Помогите Васе найти отрезок минимальной длины, который ему нужно пройти пешком, чтобы сфотографировать хотя бы $$$K$$$ деревьев.
В первой строке заданы 4 целых числа: $$$A, B, C$$$ и $$$D$$$, $$$0 \leq A \lt B \leq 10^9$$$, $$$0 \leq C \lt D \leq 10^9$$$.
Во второй строке задано одно натуральное число $$$K$$$, $$$1 \leq K \leq 10^9$$$.
Вывести два целых числа $$$L$$$ и $$$R$$$ — концы отрезка аллеи, который нужно пройти Васе. Отрезок должен содержать хотя бы $$$K$$$ деревьев и иметь минимальную возможную длину. Несмотря на то что аллея бесконечная, вам нужно найти такие числа $$$L$$$ и $$$R$$$, что $$$0 \leq L \leq R \leq 8\cdot 10^{18}$$$. Гарантируется, что среди оптимальных ответов существует ответ, удовлетворяющий этим ограничениям. Если таких оптимальных ответов несколько, можно вывести любой из них.
Подзадача 1, 25 баллов: все входные числа не превосходят $$$5000$$$.
Подзадача 2, 25 баллов: все входные числа не превосходят $$$10^7$$$.
Подзадача 3, 50 баллов: дополнительных ограничений нет.
1 2 3 5 4
1 5
0 2 1 2 6
1000 1005
В первом примере Вася может сфотографировать дерево в точке 1, два дерева в точке 3 и дерево в точке 5. Другой возможный оптимальный вариант — пройти от точки 5 до точки 9, длина пути так же будет равна 4. Более короткого маршрута, содержащего хотя бы 4 дерева, не существует.
Во втором примере в каждой точке находится ровно по одному дереву (с одной стороны деревья на четных позициях, с другой — на нечетных). Любой маршрут длины 5 будет содержать 6 деревьев.
В обычной жизни для записи некоторого момента времени можно использовать разные форматы. В этой задаче мы будем использовать следующий формат: 'hh:mm DD.MM.Y' (без кавычек), где:
- hh — количество часов, $$$00 \le hh \le 23$$$;
- mm — количество минут, $$$00 \le mm \le 59$$$;
- DD — номер дня в месяце, $$$01 \le DD \le 31$$$;
- MM — номер месяца в году, $$$01 \le MM \le 12$$$;
- Y — номер года, $$$1000 \le Y \le 2\cdot 10^9$$$.
Обратите внимание, что значения 'hh', 'mm', 'DD', 'MM' содержат ровно по две десятичных цифры, в том числе они могут содержать ведущие нули. В свою очередь, значение 'Y' записывается без ведущих нулей и может содержать от 4 до 10 цифр. Между временем ('hh:mm') и датой ('DD.MM.Y') находится ровно один пробел.
Например, первая Нижегородская городская олимпиада школьников по информатике началась 19 февраля 2005 года примерно в 10:00. Эта дата будет записана следующим образом: '10:00 19.02.2005'. Последняя минута 2021 года будет записана как: '23:59 31.12.2021'.
Момент времени будем называть 'счастливым', если значения 'hh', 'mm', 'DD', 'MM' равны и совпадают с записью последних двух цифр года 'Y'. Например, моменты '08:08 08.08.2008' и '12:12 12.12.12312' — счастливые, а '01:02 03.04.2005' и '08:08 08.08.2018' — нет.
Вам даны два момента времени. Требуется посчитать, сколько между ними (включительно) счастливых моментов времени.
В первой строке задан первый момент времени в соответствии с форматом, указанном в условии.
Во второй строке задан второй момент времени.
Гарантируется, что оба момента времени корректны. В частности, значение 'DD' не превосходит количество дней в месяце 'MM' с учетом високосности года 'Y'. Гарантируется, что второй момент времени наступает не раньше первого.
Вывести одно число — количество счастливых моментов времени между первым и вторым включительно.
Подзадача 1, 60 баллов: $$$Y \lt 10^5$$$ для обоих моментов времени.
Подзадача 2, 40 баллов: дополнительных ограничений нет.
10:00 19.02.2005 12:00 30.01.2007
2
11:00 15.05.2021 16:00 15.05.2021
0
00:00 01.01.9999 01:01 01.01.10001
1
В первом примере в указанном интервале два счастливых момента времени: '05:05 05.05.2005' и '06:06 06.06.2006'.
Во втором примере счастливых моментов времени нет — номер дня никогда не совпадет с последними цифрами года.
В третьем примере один счастливый момент времени — он соответствует второй строке входных данных.
В провинции Скайрим, а если быть точнее, в городе Вайтран вполне себе припеваючи поживал придворный маг Фаренгар Тайный Огонь, но недавно началась суматоха с возвращением драконов и появлением драконорождённого, обычные будни...
«Ходят слухи, что драконорождённый уже прибыл в Вайтран, интересно, кто это — может быть высокий или тёмный эльф, у которых есть врождённая способность к магии, а может Бретонец! Нас явно ждут разговоры о рунах и заклинаниях целыми днями...» — думал про себя Фаренгар. Надо ли говорить, как он удивился, когда увидел перед собой орка в тяжёлых доспехах, который с большим трудом разговаривал на человеческом.
Ярл$$$^{\text{∗}}$$$ Вайтрана приказал Фаренгару собрать Драконорождённого в поход и выдать ему магические посохи. Но, как мы знаем, орки не отличаются интеллектом, поэтому каждым выданным Фаренгаром магическим посохом драконорождённый может ударить врага только один раз, после чего посох ломается, а врагу наносится урон, равный длине посоха. У Фаренгара изначально нет посохов, но есть $$$N$$$ заклинаний, $$$i$$$-е из которых может создать посох веса $$$w_i$$$ и длины $$$l_i - c_i \cdot k$$$ для любого неотрицательного $$$k$$$. К сожалению, каждое заклинание с каждым конкретным $$$k$$$ можно использовать не более одного раза. (При этом разные заклинания с одним и тем же $$$k$$$ использовать можно, но каждое не более одного раза.) Фаренгар — сильный маг, он может создать сколько угодно посохов (в рамках описанных ограничений), и даже физика для него не препятствие, он вполне может создавать посохи отрицательной длины, но есть ли в этом смысл...
Всего драконорождённый может нести на себе вес $$$W$$$, поэтому ваша задача помочь Фаренгару собрать драконорождённого в путь, создав ему такие посохи, чтобы он мог нанести суммарно как можно больше урона.
$$$^{\text{∗}}$$$Ярл (др.-сканд. Jarl) — один из высших титулов в иерархии в средневековой Скандинавии.
В первой строке входных данных содержатся два целых числа $$$N$$$ и $$$W$$$ — количество заклинаний и вес, который может выдержать драконорождённый ($$$1 \leq N \leq 200\,000$$$, $$$1\leq W\leq 3000$$$).
В следующих $$$N$$$ строках содержится по три числа $$$w_i$$$, $$$l_i$$$ и $$$c_i$$$ — параметры $$$i$$$-го заклинания ($$$1\leq w_i\leq 3000$$$, $$$1 \leq l_i \leq 100\,000$$$, $$$1\leq c_i\leq l_i$$$)
Выведите максимальный урон, который драконорождённый сможет нанести всеми посохами, которые ему создаст Фаренгар.
Подзадача 1, 10 баллов: $$$N \leq 400$$$, $$$W \leq 2500$$$.
Подзадача 2, 50 баллов: $$$N \leq 50000$$$.
Подзадача 3, 40 баллов: дополнительных ограничений нет.
2 10 5 5 5 2 6 2
15
5 15 2 1 1 2 2 1 2 3 1 2 4 1 2 5 1
24
2 10 3 4 2 2 1 1
7
В первом примере оптимально создать посох первого типа с $$$k = 0$$$ и два посоха второго типа с $$$k \in [0;1]$$$, суммарный вес будет 9, а суммарный урон максимален.
Во втором примере оптимально создать посохи пятого типа с $$$k \in [0;3]$$$, четвёртого типа с $$$k \in [0;1]$$$ и третьего типа с $$$k = 0$$$, суммарный вес равен 14.
В третьем примере оптимально создать два посоха первого типа с $$$k \in [0;1]$$$ и один посох первого типа с $$$k = 0$$$, все остальные возможные посохи будут иметь неположительную длину, поэтому они не улучшат ответ.
Однажды стране Берляндии очень понадобились деньги, и было принято решение продать прекрасный парк с тыквами. К большому счастью правителей Берляндии, в мире есть ровно один бизнесмен, который может выкупить этот парк — Divan.
Узнав о таком заманчивом предложении, Divan первым делом поинтересовался, а что же представляет собой этот парк? Ему ответили, что это множество тыкв. Некоторые из них соединены между собой дорогами, да так, что между любой парой тыкв существует лишь один путь. (Строго говоря, парк — это дерево с тыквами в вершинах.) Всего парк состоит из $$$n$$$ тыкв.
Такой ответ устроил бизнесмена, и обсуждение сделки продолжилось. Так как парк тыкв — не особо практичная вещь, Divan хочет, чтобы она была удивительной. Узнав план парка, Divan решил, что будет водить по нему своих друзей. Для этого он разработает несколько маршрутов. Каждый маршрут будет задаваться парой вершин $$$(v, u)$$$. Это значит, что маршрут начинается в $$$v$$$ и идет до $$$u$$$ по единственному пути.
Так как друзья бизнесмена не очень впечатлительны, их нельзя удивить тыквами размера меньше, чем они видели. Проще говоря, до начала прогулки они не видели ни одной тыквы. Дальше, когда они идут по маршруту, каждый раз при виде тыквы большего размера, чем все ранее увиденные, друзья будут удивляться. Divanу интересно, сколько раз его друзья будут удивляться для каждого маршрута.
Так как Divan — самый богатый бизнесмен мира, он не утруждает себя логичностью построения маршрутов. Он просто выдумывает их и спрашивает у государства Берляндии: а если бы я повел друзей из $$$v$$$ в $$$u$$$, то сколько раз они бы удивились? После чего ждет ответа, и все повторяется заново, пока Divan не устанет. А это может быть ой как не скоро, ведь он готов задать $$$q$$$ вопросов.
Помогите правительству побороть кризис, ответив на все вопросы Divanа.
На первой строке входных данных находится два числа $$$n$$$ и $$$q$$$ — количество тыкв в парке и количество вопросов ($$$1 \leq n \leq 200\,000$$$, $$$1 \leq q \leq 200\,000$$$).
На второй строке входных данных находятся $$$n$$$ целых чисел $$$W_1$$$, $$$W_2$$$, ..., $$$W_n$$$ — размер тыкв ($$$1 \leq W_i \leq n$$$).
Далее следует $$$n-1$$$ строка, в каждой из которых записано два числа $$$a$$$ и $$$b$$$ ($$$1 \leq a, b \leq n$$$, при этом $$$a \neq b$$$) — номера тыкв, которые соединяет очередная дорога.
Гарантируется, что от любой тыквы к любой другой можно пройти, и притом единственным способом.
Далее следует $$$q$$$ строк, каждая из которых содержит два числа $$$x_i$$$ и $$$y_i$$$ ($$$0 \leq x_i, y_i \leq n$$$) — зашифрованный запрос.
Для того чтобы узнать настоящий запрос, нужно положить $$$v_i = (x_i + p) \bmod n + 1$$$, $$$u_i = (y_i + p) \bmod n + 1$$$, где $$$v_i$$$ — начало пути для очередного запроса, $$$u_i$$$ — конец пути, $$$p$$$ — ответ на предыдущий запрос, а $$$\bmod$$$ — операция взятия остатка от деления. Для первого запроса $$$p = 0$$$.
Для каждого запроса выведите одно целое число — сколько раз удивятся друзья Divanа, если их провести по такому маршруту.
Подзадача 1, 40 баллов: $$$n, q \le 5000$$$.
Подзадача 2, 60 баллов: дополнительных ограничений нет.
6 3 2 4 2 1 3 1 1 3 2 3 3 4 5 3 6 5 5 1 0 3 5 1
3 2 1
Парк тыкв в примере можно схематично изобразить следующим образом:
где окружности представляют собой тыквы. Внутри окружности подписан номер соответствующей тыквы, а снаружи — её размер.
В примере $$$n=6$$$ и заданы три запроса. Первый зашифрованный запрос — $$$x_1 = 5, y_1 = 1$$$. Поскольку $$$p=0$$$, получаем настоящий запрос $$$u_1 = (5 + 0) + 1 = 6$$$, $$$v_1 = (1 + 0) + 1 = 2$$$. Маршрут между этими тыквами проходит через тыквы — $$$6, 5, 3, 2$$$, соответственно, их размеры равны $$$1, 3, 2, 4$$$. На этом маршруте друзья будут удивляться 3 раза — при виде тыкв с размерами $$$1, 3, 4$$$.
Второй зашифрованный запрос — $$$x_2 = 0, y_2 = 3$$$. Поскольку ответ на предыдущий запрос — 3, то получаем $$$u_2 = (3 + 0) + 1 = 4, v_2 = (3 + 3) \bmod 6 + 1 = 1$$$. Маршрут проходит через тыквы $$$4, 2, 1$$$ с размерами $$$1, 2, 2$$$. Друзья удивятся при виде первых двух тыкв, поэтому ответ — 2. Обратите внимание, что при виде второй тыквы размера $$$2$$$ друзья не удивляются.
В третьем запросе $$$x_3 = 5, y_3 = 1$$$, $$$u_3 = (5 + 2) \bmod 6 + 1 = 2$$$, $$$v_3 = (1 + 2) + 1 = 4$$$. Маршрут проходит через тыквы $$$2, 3, 4$$$ размерами $$$4, 2, 1$$$. Друзья удивляются только при виде первой тыквы маршрута. Обратите внимание, что зашифрованный запрос совпадает с первым: $$$x_3 = x_1 = 5$$$, $$$y_3 = y_1 = 1$$$. Однако, поскольку ответ на предыдущий запрос ($$$p$$$) изменился, то реальные значения $$$u_3, v_3$$$ отличаются от первого запроса, поэтому ответ на него тоже другой.