Сложно писать олимпиады, когда не понимаешь, как они могут помочь тебе в дальнейшем. Поэтому после очередного проигрыша дух в команде упал и желание писать олимпиадки куда-то ушло. Тренер вовремя заметил это и решил что-то предпринять – ведь он-то понимает, куда может завести участие во всех этих мероприятиях. После долгих раздумий он понял — нужно просто показать команде её перспективы! Тогда он, для простоты, представил все возможные варианты развития карьеры после участия в олимпиадах в виде корневого дерева. Каждая его вершина — некоторая должность в престижной IT-компании, а рёбра проведены между должностями только если возможен карьерный рост с одной должности на другую. Естественно, участие в олимпиадах позволяет легче продвигаться по этому дереву, и тренер поспешил показать это дерево команде!

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

Помогите тренеру промотивировать ребят — найдите необходимое множество должностей.

Формально говоря, вам дано корневое дерево на N вершинах, и вам надо выбрать K вершин так, чтобы их наименьший общий предок был как можно дальше от корня.

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

Помимо работы системным администратором Дементий очень любит выращивать валерьянку и добавлять её в чай.

На столе у Дементия карта его одномерного поля валерьянки. Сегодня он планирует собрать урожай. Дементий скашивает стебли валерьянки специальной косилкой, лезвия которой висят над землёй на определённой высоте, которую можно регулировать. Дементий $$$K$$$ раз задаётся вопросом — сколько валерьянки он соберёт, если повесит лезвия на $$$L$$$ сантиметров над землёй?

Формально, количество собранной Дементием валерьянки определяется по формуле:

где $$$L$$$ – высота лезвий, $$$a_i$$$ – высота $$$i$$$-го кустика валерьянки.

Недавно Домин заказал в интернет-магазине условие для одной из задач, и теперь ожидает его доставки по почте. Домин живет в стране, состоящей из n городов, причем между некоторыми городами u и v есть двустороннее почтовое сообщение, которое работает лишь в w-й день недели (всего в неделе 7 дней). Также доставку можно произвести из любого города в любой другой (возможно, через другие города). Посылка может быть отправлена утром из одного города по открытому сообщению и прибыть в другой к вечеру, или пролежать в почтовом отделении несколько дней, пока сообщение не заработает.

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

В математической статистике есть такое понятие, как медиана ряда чисел. Медианой ряда чисел называется число, стоящее посередине упорядоченного по возрастанию ряда чисел (в случае, если количество чисел нечётное). Если же количество чисел в ряду чётно, то медианой ряда является полусумма двух стоящих посередине чисел упорядоченного по возрастанию ряда.

Но в Ярославском университете не дремлют и изобрели новое понятие – медиана профессора Р. Определим её. Медианой профессора Р. ряда чисел называют число из этого ряда, ближайшее к полусумме минимального и максимального, причем, если таких чисел несколько, из них выбирается минимальное по значению. Ваша задача – найти медиану Профессора Р. в заданном ряде чисел.

В далекие времена, о которых никто не помнит, проходил турнир горцев. Турнир этот был не на жизнь, а на смерть, но за жизнь! В турнире принимали участие n горцев, выстроившихся в шеренгу. Каждый боец был наделен силой, сила i-го горца определялась величиной p_i, при этом отметим, что не было горцев с одинаковой силой. Сам турнир проводился в m этапов. До начала каждого сражения великий вождь Гыда выбирал несколько подряд выстроившихся горцев из шеренги. Выбранная группа начинала сражение, где каждый сражался сам за себя, побеждал сильнейший. После битвы победитель вставал на свое место в шеренге, затем шеренга смыкалась и бойцы опять стояли плечо к плечу. Вам требуется вывести силы бойцов в шеренге после окончания турнира.

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

Квадратная страна имеет ширину $$$x_{max}$$$ ($$$1 \leq x_{max} \leq 10^4$$$) и длину $$$y_{max}$$$ ($$$1 \leq y_{max} \leq 10^4$$$). Железнодорожная сеть состоит из $$$n$$$($$$1 \leq n \leq 10^4$$$) стрелок и двух таможен, которые соединены $$$m$$$ ($$$1 \leq m \leq 30000$$$) прямыми отрезками железной дороги. Координаты стрелок $$$(x_i, y_i)$$$ – целые числа, координаты таможенных пунктов $$$(s, 0)$$$ $$$(t, y_{max})$$$ также целые, и лежат на противоположных границах. Отрезки железной дороги соединяют только стрелки (и таможенные пункты), и не пересекаются в других точках. Координаты всех стрелок и таможенных пунктов различны.

Через отрезок железной дороги между двумя стрелками может проследовать поезд длины не превосходящий длину этого отрезка. Длина отрезка дороги, соединяющего две стрелки (или таможни) – это расстояние между точками на плоскости. Длина поезда – это количество вагонов в нем. Все вагоны одинаковы, и имеют длину $$$1$$$. Таким образом, через отрезок длины $$$4.5$$$ может проехать поезд не более чем из $$$4$$$ вагонов, а через через отрезок длины $$$10$$$ – не более $$$10$$$ вагонов.

Поезд может двигаться по железной дороге в любом направлении. Более того, он может в произвольный момент остановиться и сменить направление движения на противоположное. Поезд не может занимать одновременно более чем одну стрелку (но может касаться их своими концами). При прохождении стрелки, состав не может отклониться более чем на $$$60$$$ градусов от прежнего направления движения (то есть, поезд не может изгибаться произвольно – угол между соседними вагонами не может быть острее $$$120$$$ градусов).

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

Строки прогресса часто используются для отображения текущего состояния работающего процесса. Одним из видов таких строк являются блочные. Блочная строка состоит из $$$n$$$ одинаковых блоков. Для отображения прогресса, доля выполнения которого составляет $$$p$$$ ($$$0 \leq p \leq 1$$$), это число умножается на $$$n$$$, и полученное число округляется к ближайшему целому. Получается число $$$k = round(p \cdot n)$$$. Далее, в строке прогресса отображается $$$k$$$ блоков.

Если процессы работают быстро, то очень редко можно увидеть полностью заполненную строку, поэтому $$$n$$$ можно определить не всегда. Пусть нам удалось посчитать число блоков $$$k_1$$$ для процесса, выполнившего треть работы ($$$p = 1/3$$$), и число $$$k_2$$$ для процесса? отработавшего наполовину ($$$p = 1/2$$$). Определите, какие числа $$$n$$$ подходят под эти условия, или сообщите, что таких чисел нет.

Из клетчатого поля размером $$$n$$$ строк и $$$m$$$ столбцов ($$$5 \leq n, m \leq 1000$$$) вырезали внутреннюю часть размером $$$(n-4)\times(m-4)$$$ так, что по сторонам остались полоски шириной 2 клетки.

На левой верхней клетке поля стоит шахматный конь. Можно ли, используя только узкие бордюры шириной 2 клетки, обойти конем вокруг выреза и вернуться на исходную клетку? И если да, то какое минимальное число ходов для этого необходимо (конь ходит по шахматным правилам)?

Например, если есть поле $$$5\times5$$$ (вырезана клетка $$$(3, 3)$$$), то конь может обойти вокруг выреза за $$$4$$$ хода: $$$(1, 1) \rightarrow (3, 2) \rightarrow (4, 4) \rightarrow (2, 3) \rightarrow (1, 1)$$$.

Примечание. В момент движения конь не может перескакивать через вырезанные клетки.

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

Дело в том, что пирамиды всех предыдущих фараонов имели одинаковые размеры, и на это были серьезные причины. Для строительства пирамиды необходимо заложить надежный фундамент из крепкого гранита. Гранит надлежащего качества добывался на единственной каменоломне в виде абсолютно одинаковых кубов. Перевозка этих кубов была непростым делом, и за одну перевозку с каменоломни доставляли ровно $$$n$$$ ($$$1 \leq n \leq 10^9$$$) таких гранитных блоков. Так как основание пирамиды должно быть идеальным квадратом, то все предшествующие фараоны просто совершали $$$n$$$ перевозок и строили пирамиды на основании из $$$n^2$$$ блоков.

Фараон hEx хочет построить свою пирамиду на более крупном фундаменте. Он уже запланировал обязательные $$$n$$$ перевозок по $$$n$$$ кубов, но для увеличения фундамента потребуются дополнительные перевозки. Фараон хочет сделать минимально возможное количество сверхплановых перевозок $$$p$$$. Также он требует, чтобы объем единичной перевозки не сокращался (все те же $$$n$$$ блоков), и чтобы после укладки квадратного фундамента лишних блоков не осталось.

Рассмотрим пример. Пусть $$$n = 4$$$, тогда за $$$4$$$ плановых перевозки будут получены $$$16$$$ блоков, из которых можно уложить фундамент $$$4\times4$$$. Если добавить одну сверхплановую перевозку ($$$p = 1$$$), то будет $$$20$$$ каменных кубов, из которых не получится выложить квадрат, значит $$$p$$$ не может быть единицей. Аналогично, для $$$p = 2, 3, 4$$$ получаем $$$24$$$, $$$28$$$ и $$$32$$$ куба, что также не позволяет уложить их в виде квадрата без остатков. Наконец, при $$$5$$$ сверхплановых поставках получаем $$$36$$$ кубических блоков, из которых можно построить фундамент $$$6\times 6$$$. Значит для $$$n = 4$$$ получим $$$p = 5$$$.

Играя в одну из популярных игр, программист Вася столкнулся с интересной задачей.

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

Для более гибкого управления, конвейерные ленты могут объединяться с помощью устройства, под названием «merger» или разъединяться с помощью устройства «splitter».

Устройство «merger» имеет 3 входа и один выход. Просматривая входы по очереди, устройство перекладывает предметы с входных конвейерных лент на выходную. Для корректной работы «merger»-а необходимо, чтобы предметы подавались конвейером хотя бы на один вход, и снимались с выхода (если выходному конвейеру будет некуда транспортировать предметы, или выходной конвейер остановится из-за переполнения, то устройство остановится).

Устройство «splitter» имеет 1 вход и 3 выхода. Принимая предметы со входного конвейера, «splitter» равномерно, по очереди, перемещает их на подключенные выходные конвейеры. То есть, если все три выхода подключены к работающим конвейерам, то входной поток будет разделен на 3 одинаковых (по 1/3), а если подключены только 2 выхода, то поток разделяется на 2 одинаковых (по 1/2).

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

Пусть у нас имеется соотношение n:m ($$$1 \leqslant n, m; n+m \leqslant 10^{6}$$$). Предложите схему соединения «splitter»-ов и «merger»-ов, которая разбивает входной поток в пропорции $$$n$$$ к $$$m$$$, используя при этом, суммарно, не более 48 «splitter»-ов и «merger»-ов. В вашей схеме не должно быть стоящих конвейеров и устройств. Если есть несколько таких схем, правильной считается любая их них.

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

Играя в одну из популярных игр, программист Вася столкнулся с интересной задачей.

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

Для более гибкого управления, конвейерные ленты могут объединяться с помощью устройства, под названием «merger» или разъединяться с помощью устройства «splitter».

Устройство «merger» имеет 3 входа и один выход. Просматривая входы по очереди, устройство перекладывает предметы с входных конвейерных лент на выходную. Для корректной работы «merger»-а необходимо, чтобы предметы подавались конвейером хотя бы на один вход, и снимались с выхода (если выходному конвейеру будет некуда транспортировать предметы, или выходной конвейер остановится из-за переполнения, то устройство остановится).

Устройство «splitter» имеет 1 вход и 3 выхода. Принимая предметы со входного конвейера, «splitter» равномерно, по очереди, перемещает их на подключенные выходные конвейеры. То есть, если все три выхода подключены к работающим конвейерам, то входной поток будет разделен на 3 одинаковых (по 1/3), а если подключены только 2 выхода, то поток разделяется на 2 одинаковых (по 1/2).

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

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

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

Премьер-министр Борляндии, опасаясь, что его электронная почта может быть взломана и переписка станет достоянием общественности, обратился за помощью в лабораторию компьютерной безопасности Борляндского университета, работники которой придумали новый метод шифрования. Они установили, что премьер-министр пишет тексты, состоящие из цифр и строчных латинских букв, количество символов в которых равно в точности степеням двойки, и придумали следующий метод шифровки сообщения – все символы склеиваются в одну большую строку длины 2ⁿ. Затем они переворачивают строчку, потом делят ее на две и переворачивают каждую половину, потом делят ее на четыре части и переворачивают каждую четверть, ... , потом он делят ее на 2^n - 1 и переворачивают каждую часть. Однако возникла небольшая сложность – ученые ещё не придумали, как восстанавливать первоначально заданную строку. Ваша задача – помочь им написать программу для дешифровки сообщения.

Программист Вася любит хоккей и болеет за самый лучший в мире клуб «200 OK». В хоккее Васе нравятся две вещи: победа любимой команды и красивый счет на табло. При этом красоту игрового счета Вася понимает своеобразно. Так, он называет игру красивой, если каждый период завершился с красивым результатом. Тут стоит пояснить, что хоккейный матч состоит из трёх периодов, а результат каждого периода записывают парой целых неотрицательных чисел. Например, результаты матча могут выглядеть так: $$$(3:0)$$$, $$$(1:3)$$$, $$$(1:1)$$$. Такая запись означает, что в первом периоде первая команда забросила три шайбы, вторая - $$$0$$$; во втором периоде первая забросила $$$1$$$ шайбу, вторая - $$$3$$$; наконец, в третьем периоде обе команды забросили по одной шайбе. В такой игре со счетом $$$5:4$$$ победила первая команда.

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

Вася — болельщик со стажем, он давно понял, что существуют ровно $$$22$$$ различных красивых игры, в которых побеждает первая команда (две игры считаются различными, если они отличаются результатом хотя бы одного периода). Однако это справедливо только для матча, состоящего из $$$3$$$ периодов.

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

Помогите Васе найти решение, пока матч не начался.

Команда чемпионов по спортивному программированию участвовала в очередных важных соревнованиях, которые длятся $$$K$$$ минут. Они проводились по обычным правилам АСМ, но ребята узнали, что в системе подсчета результатов не всегда верно подсчитывалось штрафное время. А именно, когда штрафное время становилось больше, чем 23 часа 59 минут, то из него вычиталось 24 часа.

Чемпионы, получив набор из $$$N$$$ задач, мгновенно могли определить для каждой из них время $$$t_i$$$ (в минутах), которое потребуется им для того, чтобы решить и отладить программу решения $$$i$$$-й задачи. При этом все задачи чемпионы всегда сдают с первой попытки. Как истинные спортсмены, ребята во время соревнований не тратят ни одной минуты впустую. Как только они сдают очередную задачу, так сразу же начинают решать следующую. Зная об ошибке в подсчете штрафных минут, они хотят определить наилучший результат, который могут показать, если сдавать нужные задачи в нужном порядке. Составьте программу, которая поможет им это сделать.