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

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

1. Удаление пустых строк. Строка считается пустой, если содержит только пробельные символы.
2. Склейка строк, имеющих на конце символ переноса строки. Символом переноса является символ доллара $, за которым может следовать любое количество пробельных символов. Склейка осуществляется следующим образом: из потока символов исключаются символы, начиная с доллара, и следующие за ним пробельные символы до конца строки (включая сам перевод строки).
3. Удаление строк с комментариями. В языке есть только однострочные комментарии. Строки с комментарием начинаются с двойного знака доллара: $$, за которыми следует как минимум один непробельный символ. С начала строки и до двойного доллара $$ допустимы только пробельные символы – наличие перед ним иных символов означает, что это не комментарий.

   Комментарий продолжается до конца строки и не может быть перенесен на следующую с помощью символа переноса. Строка комментария удаляется целиком, включая ведущие пробельные символы (если они есть).

Пробельными символами в языке считаются пробелы (код 32) и табуляции (код 9).

Программа всегда завершается пустой строкой.

Преобразования осуществляются в указанном порядке:

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

Напишите программу, которая произведет препроцессинг описанного типа.

Хакер Кирилл решил разработать новый генератор случайных чисел. Для этого он взял два больших числа $$$ n $$$ и $$$ m $$$, превратил их в степени двойки, сложил, и полученную сумму возвёл в небольшую степень $$$ k $$$, и получил некоторое число $$$ r = (2^n + 2^m)^k $$$. Случайные числа предполагалось вырезать из двоичной записи числа $$$ r $$$.

Когда Кирилл опубликовал свои идеи на форуме, один из коллег сказал, что полученные числа будут слишком неслучайны, указав, что даже просто количество единичных битов в двоичной записи числа $$$ r $$$ слишком предсказуемо.

Помогите Кириллу проверить утверждение коллеги. Напишите программу, которая по числам $$$ n $$$, $$$ m $$$ и $$$ k $$$ определит количество единичных битов в двоичной записи числа $$$ r = (2^n + 2^m)^k $$$.

Для восстановления популяции слонов в одной африканской стране было предложено создать специализированную ферму. Под ферму был выделен участок саванны размером $$$ n \times m $$$ километров. Численность стада слонов такова, что за день оно съедает растительность на 1 кв. километре, после чего его следует перевести на другой участок.

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

Установлено, что для поддержания максимально естественного процесса питания слоны должны питаться по $$$ k $$$ дней подряд одной и той же травой. Каждый участок будущего пастбища планируется засеять одним видом травы, и всего будет задействовано $$$ p $$$ их разновидностей.

Чтобы растительность между визитами стада максимально восстанавливалась, было предложено составить циклический маршрут таким образом, чтобы он:

• был максимально длинным;
• пересекал только вертикальные или горизонтальные границы участков;
• не содержал самопересечений;
• состоял из $$$ p $$$ отрезков, засеваемых одинаковой травой, по $$$ k $$$ участков в каждом.

Напишите программу, которая по заданным числам $$$ n $$$, $$$ m $$$, $$$ k $$$ и $$$ p $$$ построит маршрут стада слонов, либо сообщит что такого решения нет.

Нике нравится сказка про репку. Всем известна сказка про репку, где общим трудом её смогли вытащить из земли. Дедка за репку, бабка за дедку, внучка за бабку, жучка за внучку, кошка за жучку, мышка за кошку. Ника заинтригована вопросом: «Неужели мышка такая сильная?»

Вам известны показатели силы каждого из $$$n$$$ помощников. Сила $$$i$$$-го помощника равна $$$a_i$$$. Нике достоверно известно: чтобы вытащить репку, необходимо приложить минимум $$$x$$$ силы. Помощников в ряду можно поменять местами произвольным образом. Когда помощники начнут тянуть репку, их суммарная сила будет равняться $$$\displaystyle\sum_{i=1}^n\dfrac{b_i}{i}$$$, где $$$i$$$ – номер помощника в ряду (первый стоит дальше всех от репки, $$$n$$$-й держится за репку), $$$b_i$$$ – его сила.

Помогите Нике определить, могут ли помощники вытащить репку.

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

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

Определите, в каких деревнях установить одну или две станции и какие должны быть их радиусы покрытия R₁ и R₂, чтобы сумма R₁² + R₂² получилась минимальной и чтобы при этом каждая деревня оказалась в зоне покрытия хотя бы одной станции. В случае установки одной станции радиус покрытия второй можно считать равным нулю.

Все деревни небольшие, поэтому их можно считать точками. Если какая-то станция обслуживает единственную деревню (в которой она установлена), то её радиус покрытия считайте равным 1.

Помимо бинарных деревьев на парах по дискретной математике Профессор Р. также рассказывает об ориентированных деревьях. Дадим определение направленного дерева. Ориентированное (направленное) дерево — ациклический ориентированный граф, в котором только одна вершина имеет нулевую степень захода (в неё не ведут дуги), а все остальные вершины имеют степень захода 1 (в них ведёт ровно по одной дуге). Вершина с нулевой степенью захода называется корнем дерева, вершины с нулевой степенью исхода (из которых не исходит ни одна дуга) называются концевыми вершинами или листьями. На рисунке ниже показан пример ориентированного дерева.

После занятия по ориентированным деревьям профессор задал студентам на дом следующую задачу.

Покрасим все вершины ориентированного дерева в некоторые цвета (обозначим через $$$c_i$$$ цвет вершины с номером $$$i$$$). После этого для каждой вершины $$$i$$$ профессор хочет узнать, какой цвет встречается чаще всего в поддереве, корнем которого является вершина с данным номером $$$i$$$.

Как ни старались студенты, они не смогли придумать, как решить эту задачу. Помогите им – напишите программу, которая ответит на все запросы, составленные профессором Р.

Профессор Р. помимо преподавания в университете принимает участие в соревнованиях по программированию как составитель задач. Сегодня профессора Р. посетила светлая мысль – он решил создать рейтинг-лист вузов, участвовавших в четвертьфинальных соревнованиях по спортивному программированию, проводимых в городе Киберславль. Для подсчёта рейтинга профессор придумал формулу:

где $$$R$$$ – общий рейтинг, $$$R_0$$$ – рейтинг последнего года, $$$R_1$$$ – рейтинг предыдущего года, $$$R_2$$$ – рейтинг года двухлетней давности. Рейтинг вуза по итогам года считается по формуле:

где $$$R_y$$$ – рейтинг вуза за год, $$$k$$$ – число задач, решённых сильнейшей (сильнейшей считается команда, решившая больше всех задач, при равенстве задач сильнейшей считается команда, занявшая более высокое место) командой вуза в четвертьфинале, $$$a, b, c$$$ – премиальные очки за занятые места, полученные первой, второй и третьей командами вуза в четвертьфинале (если второй и третьей команды не было, они вносят в рейтинг 0 баллов).

Премиальные очки за места в четвертьфинале начисляются следующим образом: 50-е место приносит команде 1 балл, 49-е – 2 балла и т. д. с шагом 1 до 11 места включительно, которое таким образом «стоит» 40 баллов. Далее, 10 место приносит 42 балла, 9-е – 44, 8-е – 46, 7-е – 48, 6-е – 50, 5-е – 53, 4-е – 57, 3-е – 62, 2-е – 68 и, наконец, 1-е – 80 баллов.

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

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

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

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

Новая игра ведется на клетчатом поле размером $$$ 1 \times n $$$. Клетки поля пронумерованы числами от 1 до $$$ n $$$ слева направо.

Петя прячет на поле единственный корабль длиной $$$ k $$$ палуб.

Вася пытается найти корабль, загадывая числа $$$ t $$$ и сообщая их Пете. В ответ на сообщенное число $$$ t $$$ Петя вычисляет число $$$ r $$$ – сколько раз бы произошло попадание в корабль, если бы стреляли по клеткам $$$ t, 2t, 3t, ..., r \times t, ... $$$. Результаты попыток записываются в протокол. Вася может сделать $$$ c $$$ попыток и выигрывает, если точно определяет положение корабля Пети.

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

Читая старый учебник по алгебре, профессор Р. наткнулся на интересные числовые последовательности, называемые последовательностями Грея. Первая последовательность Грея состоит из числа $$$1$$$, вторая последовательность Грея состоит из чисел $$$1, 2, 1$$$, третья последовательность Грея равна $$$1, 2, 1, 3, 1, 2, 1$$$ и т. д., последовательность Грея с номером $$$i$$$ состоит из $$$(i - 1)$$$-й последовательности Грея, числа $$$i$$$ и вновь записанной $$$(i - 1)$$$-й последовательности Грея. Профессор обозначил через $$$f(n)$$$ сумму чисел в $$$n$$$-й последовательности Грея и просит вас написать программу, которая найдёт правильный ответ для заданного $$$n$$$. Так как эта сумма может оказаться очень большой, он просит посчитать остаток от деления суммы на число $$$10^9 + 9$$$.

Это интерактивная задача.

Брат профессора Р. доктор Р. является фармацевтом и работает в одной из аптек Киберславля. Сегодня ему в аптеку пришла партия из $$$N$$$ баночек с таблетками лекарства для укрепления памяти, в каждой баночке $$$N$$$ таблеток. Однако случилась беда: выяснилось, что все таблетки в одной из баночек оказались поддельными. Известно, что каждая таблетка с настоящим лекарством весит $$$500$$$ миллиграмм, а каждая поддельная таблетка весит $$$501$$$ миллиграмм. У доктора Р. есть точные весы, которые показывают суммарный вес таблеток, которые на них положили. Доктор Р. хочет за одно взвешивание узнать, в какой баночке лежат фальшивые таблетки. Чтобы это было удобнее сделать, он пронумеровал баночки числами от $$$1$$$ до $$$N$$$, однако так и не придумал, как правильно сделать одно взвешивание. Доктор попытался обратиться с этим вопросом к брату, однако тот уехал на научную конференцию и оказался недоступен. Поэтому доктор Р. просит вас помочь ему определить баночку с фальшивыми таблетками.

Сначала на вход вашей программе подаётся число $$$N$$$ $$$(1 \le N \le 10^5)$$$ – количество баночек с таблетками.

После этого ваша программа может делать запрос:

1. В первой строке нужно вывести $$$K$$$ $$$(1 \le K \le N)$$$ – количество открываемых баночек.
2. В следующих $$$K$$$ строках нужно вывести в выходной поток пары чисел $$$x~y$$$ $$$(1 \le x \le N, 1 \le y \le N)$$$, где $$$x$$$ – номер баночки, $$$y$$$ – количество таблеток, которые кладутся на весы. Никакая баночка не должна быть указана дважды.

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

После сделанного запроса вам нужно будет определить номер баночки с фальшивыми таблетками. Для этого нужно будет вывести в выходной поток в отдельной строке «$$$!~M$$$», где $$$M$$$ – номер баночки, в которой, по вашему мнению, находятся фальшивые таблетки.

Если ваша программа сделает более 1 запроса или задаст некорректный запрос (например, запросит номер баночки или количество таблеток большее $$$N$$$), она получит любой вердикт, отличный от «Accepted».

После каждого действия вашей программы выводите символ перевода строки. После вывода очередной строки обязательно используйте функции очистки потока, чтобы часть вашего вывода не осталась в каком-нибудь буфере. Например, на С++ надо использовать функцию «fflush(stdout)», в Pascal «flush(output)» на Java и Kotlin вызов «System.out.flush()» и «stdout.flush()» для языка Python.

Три колеса 1, 2 и 3 с длинами обода $$$ k $$$, $$$ l $$$ и $$$ m $$$ сантиметров свободно вращаются на осях. Оси колес закреплены на прямой балке слева направо так, что колесо 1 соприкасается с колесом 2, а колесо 2 соприкасается с колесом 3. Если вращать колесо 1, то оно передаст вращение на колесо 2, а то, в свою очередь, на колесо 3.

Через каждый сантиметр рядом с ободами колес закреплены магниты разной силы. Для простоты силу магнитов обозначим целыми числами от 1 (самый слабый магнит) до $$$ max(k, l, m) $$$ (самый сильный). Магниты первого колеса имеют силу от $$$ 1, 2, 3, ..., k $$$, второго – $$$ 1, 2, 3, ..., l $$$, третьего – $$$ 1, 2, 3, ..., m $$$. На каждом колесе магниты расположены строго по возрастанию и против направления часовой стрелки (за исключением самого сильного и слабого магнитов, стоящих рядом).

Изначально колеса расположены так, что самые слабые магниты (с силой 1) находятся в крайнем левом положении. Рядом с крайней правой точкой колеса 3 закреплен магнит с силой 200 (сильнее, чем любой магнит на колесах).

Первое колесо начинает вращаться со скоростью обода 1 см в секунду по часовой стрелке. Соответственно, второе колесо вращается с такой же скоростью, но уже против часовой стрелки. Третье колесо, с такой же скоростью, снова вращается по часовой стрелке. На магните 1 первого колеса закреплен железный шарик. В процессе вращения колес шарик может переходить со слабого магнита на более сильный, но только в точках касания колес либо с крайней правой позиции колеса 3 на магнит с силой 200.

Напишите программу, которая по заданным числам $$$ k $$$, $$$ l $$$ и $$$ m $$$, определит, окажется ли когда-нибудь шарик на магните 200, и если окажется, то через сколько секунд после начала вращения колес.

Создатели операционной системы «Икс» сделали ставку на работу в терминале и включили в дистрибутив оболочку SuperShell.

Работая в SuperShell, можно вводить название интересующего файла посимвольно либо использовать Tab для автоматического дополнения.

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

Фредди — один из разработчиков «Икс» — тестировал работу оболочки и, оказавшись в директории с логами, задумался, какое минимальное количество символов понадобится набрать на клавиатуре, чтобы открыть нужный файл. Нажатие Tab также считается вводом символа.