Сегодня на уроке занимательной математики Саше рассказали про треугольник Паскаля. В этом треугольнике на вершине и по бокам стоят единицы. Каждое число равно сумме двух расположенных над ним чисел. Так выглядят первые шесть строк в треугольнике:

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

Федя был очень обрадован существованию такого понятия как НОД чисел.

Наибольшим общим делителем (НОД) двух натуральных чисел $$$m$$$ и $$$n$$$ называется наибольший из их общих делителей. Понятие наибольшего общего делителя естественным образом обобщается на наборы из более чем двух натуральных чисел, как наибольший из общих делителей всех этих чисел.

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

Назовём наибольшим подстрочным делителем (НПД) числа наибольший общий делитель всех его непустых подстрок.

Подстрока — это непрерывная последовательность символов внутри строки. Например, у числа $$$171$$$ подстроки это числа: $$$1$$$, $$$17$$$, $$$171$$$, $$$7$$$, $$$71$$$ и $$$1$$$, а числа $$$11$$$ и $$$2$$$ не являются его подстроками.

По заданному числу $$$n$$$ найдите его НПД.

Артур и Никита, наигравшись в шахматы, придумали новую игру. У каждого игрока изначально есть по одному числу $$$a$$$ и $$$b$$$ соответственно. Сначала Артур приписывает к своему числу $$$n$$$ любых цифр справа, потом Никита приписывает к своему $$$m$$$ любых цифр справа. Побеждает тот, у кого число в итоге окажется больше. Ваша задача — научиться определять исход игры по заданным числам $$$a, b, n, m$$$, если игроки придерживаются оптимальной стратегии.

У Оли есть сад, в котором растет $$$n$$$ роз. Все розы расположены в ряд и последовательно пронумерованы числами от $$$1$$$ до $$$n$$$. Высота $$$i$$$-й розы — $$$a_i$$$ сантиметров.

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

Для того чтобы сделать сад красивым, у Оли есть волшебное удобрение, которое позволяет за одно применение моментально увеличить высоту любой розы на $$$1$$$ сантиметр. Оля не хотела бы тратить много удобрения, а потому ей необходимо узнать, чему равно минимальное количество раз, которое необходимо применить удобрение, чтобы все розы в саду стали красивыми?

Однажды Максим подумал, что было бы здорово решать задачи по программированию каждый день, это явно скрасит его жизнь. Затем он увидел, что на одном популярном сайте ведётся статистика не только по количеству дней подряд, которые Максим решает задачи, но и по количеству решённых задач за месяц (всем известно, что в месяце $$$k$$$ дней).

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

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

Известно, что он уже выполняет это условие на протяжении $$$n$$$ дней. Интересно, какое минимальное количество задач решил Максим за этот период.

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

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

Если нельзя ограничить квадрат, выведите 0.

Замок короля Темура в осаде: за стенами города появился монстр с когтистыми лапами. Чтобы изгнать монстра, волшебнику замка Эмилю потребуется много времени на произнесение отпугивающего заклинания, поэтому он просит короля сдерживать монстра как можно дольше.

Монстра задержит стена замка, которая поделена на $$$n$$$ равных по ширине частей, пронумерованных от $$$1$$$ до $$$n$$$. У каждой части стены есть своя высота $$$h_i$$$. Для того, чтобы проникнуть в замок, монстру придётся уничтожить всю стену. Уничтожение стены происходит следующим образом: монстр (у которого ровно $$$k$$$ когтей на лапах) подходит к некоторой части стены (не расходуя на это времени) и, если высота части стены делится на $$$k$$$, мгновенно эту часть уничтожает (снижает высоту до 0). В противном случае он тратит $$$1$$$ минуту времени, чтобы уменьшить высоту этой части с $$$h_i$$$ до $$$\lfloor \frac{h_i}{k} \rfloor$$$ (деление с округлением до целого вниз). Монстр повторяет эту процедуру, пока вся стена не окажется уничтожена, т.е. высота всех частей не окажется равной нулю.

Помимо стены, у Темура есть $$$m$$$ свитков с заклинаниями мощности $$$c$$$. Темур может использовать каждый из свитков, чтобы увеличить высоту одной (любой) части стены на выбранное им значение от $$$1$$$ до $$$c$$$. При этом на каждую часть стены магия подействует не более одного раза, а применять свитки можно только до того, как монстр начнёт ломать стену.

Помогите королю Темуру определить, какое наибольшее число минут сможет сдерживать стена монстра после её укрепления.

Однажды Сеня прогуливался по Калининграду и обнаружил магазин интересных графов «Остовок». Этот магазин выделялся из многих обыденных магазинов графов тем, что в нём торговали только остовами (см. определение). Зайдя в магазин, Сеня обнаружил единственный оставшийся на прилавке граф — полный граф на $$$n$$$ вершинах (обозначается $$$K_n$$$), Сеня решил купить как можно больше остовов, полная дама Люси Декарт — продавщица магазина готова отрезать от графа любой остов, который ей укажет Сеня, стоимость остова равна его диаметру (см. определение). При вырезании остова из графа вершины в последнем остаются, но пропадают рёбра, содержащиеся в этом остове.

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

Остов или остовное дерево графа — это дерево, подграф данного графа, с тем же числом вершин, что и у исходного графа.

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

Подграф — это часть графа, в которой мы берём некоторые его вершины и ребра. Другими словами, граф $$$H$$$ является подграфом графа $$$G$$$, если вершины и рёбра $$$H$$$ являются подмножеством вершин и рёбер $$$G$$$.

Диаметр графа — это число, равное расстоянию между наиболее удаленными друг от друга вершинами графа.