Последовательность целых положительных чисел назовём $$$1$$$-стабильной, если любые два соседних элемента в ней отличаются не более чем на $$$1$$$.

Про две последовательности одинаковой длины говорят, что первая лексикографически меньше второй, если первые $$$k$$$ чисел в них совпадают, а $$$(k + 1)$$$-е число в первой последовательности меньше, чем соответствующее число во второй.

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

Ясно, что из всех $$$n$$$-элементных $$$1$$$-стабильных последовательностей можно единственным образом построить лексикографически упорядоченный список. Например, для $$$n = 3$$$ этот список начинается так: $$$$$$(1, 1, 1),\; (1, 1, 2),\; (1, 2, 1),\; (1, 2, 2),\; (1, 2, 3),\; (2, 1, 1),\; (2, 1, 2),\; \ldots$$$$$$

Лексикографическим номером $$$n$$$-элементной $$$1$$$-стабильной последовательности называется её номер в лексикографически упорядоченном списке всех $$$n$$$-элементных $$$1$$$-стабильных последовательностей. Последовательности нумеруются начиная с $$$0$$$. Для любого $$$n$$$ лексикографически упорядоченный список таких последовательностей, очевидно, бесконечен. Поэтому для любого номера существует $$$1$$$-стабильная последовательность с таким лексикографическим номером.

Вам требуется написать программу, которая будет находить $$$n$$$-элементную $$$1$$$-стабильную последовательность по её лексикографическому номеру $$$x$$$.

В компании [REDACTED] думают запустить несколько проектов.

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

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

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

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

Вас, как высококвалифицированного специалиста, просят найти максимальную суммарную выручку.

Разноцветным взвешенным деревом называется дерево, у которого у каждой вершины $$$i$$$ есть вес $$$w_i$$$ и цвет $$$c_i$$$. «Хорошим» множеством разноцветного взвешенного дерева является любое подмножество вершин дерева, которое удовлетворяет следующим условиям:

• никакие две вершины в подмножестве не соединены ребром,
• все вершины в подмножестве разного цвета.

Определим вес «хорошего» множества как суммарный вес вершин в этом множестве (пустое множество имеет вес $$$0$$$).

Дано разноцветное взвешенное дерево, необходимо найти максимальный вес «хорошего» множества в нём.

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

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

От первой выпитой в течение сессии чашки Женя расслабляется на $$$x_1$$$ единиц, где $$$x_1$$$ — это коэффициент расслабления для первой выпитой чашки чая. От следующей — на $$$2 x_2$$$ единиц, где $$$x_2$$$ — это коэффициент расслабления для второй выпитой чашки чая. И так далее: от чашки, выпитой под номером $$$i$$$, Евгений расслабляется на $$$i x_i$$$ единиц.

Помогите Жене узнать, какое максимальное суммарное количество единиц расслабления он сможет получить за сессию с Да Хун Пао.

В волшебном королевстве Эквилибрия после могущественного заклинания случилась непредвиденная буря, которая затопила земли между Великой библиотекой Эквилибрии и торговым кварталом. Ваш герой, юный маг, должен пройти от библиотеки к рынку, чтобы доставить важные свитки с заклинаниями. Затопленные поля королевства представляют собой сетку размером $$$n \times m$$$, и каждая ячейка сетки содержит воду определённой глубины. Маг может перемещаться только вправо, влево и вниз по сетке ($$$(\mathit{row}, \mathit{col} + 1)$$$, $$$(\mathit{row}, \mathit{col} - 1)$$$ и $$$(\mathit{row} + 1, \mathit{col})$$$), начиная своё путешествие из верхнего левого угла ($$$(1, 1)$$$, библиотека) и заканчивая в нижнем правом ($$$(n, m)$$$, рынок). Ваша задача — найти путь, при проходе по которому максимальная глубина воды будет минимальной, чтобы ваш герой оставался как можно более сухим.

Доминошка на клетчатой плоскости — это фигура из двух клеток, имеющих общую сторону. Замощение доминошками прямоугольника из $$$m \times n$$$ клеток — это такой набор доминошек, целиком лежащих внутри прямоугольника, что каждая клетка прямоугольника покрыта ровно одной из них. Два замощения $$$P$$$ и $$$Q$$$ считаются различными, если существуют доминошки $$$p \in P$$$ и $$$q \in Q$$$, у которых ровно одна общая клетка.

Сколько существует способов замостить прямоугольник $$$m \times n$$$ доминошками? Так как количество способов может быть очень большим, нужно вывести ответ по модулю $$$10^9 + 7$$$.

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

До осени у Окорочка будет ровно $$$n$$$ походов в магазин, и для каждого похода известно $$$a_i$$$ — количество сухого риса в граммах — и $$$b_i$$$ — количество сырой куриной грудки в граммах, которые он собирается купить. Также известно, что один приём пищи Окорочка будет состоять из $$$k$$$ граммов риса и грудки в сумме. Но Окорочок решил не смешивать рис и грудку из разных походов в магазин, а потому приём пищи всегда будет иметь один из следующих типов:

• $$$x$$$ граммов риса и $$$y$$$ граммов грудки, которые были куплены в один и тот же поход в магазин, причём $$$x + y = k$$$;
• $$$x_1, x_2, \ldots, x_r$$$ граммов риса ($$$x_1 + x_2 + \ldots + x_r = k$$$), где $$$x_i$$$ — часть от всего риса, купленного в какой-то из походов в магазин;
• $$$y_1, y_2, \ldots, y_r$$$ граммов грудки ($$$y_1 + y_2 + \ldots + y_r = k$$$), где $$$y_i$$$ — часть от всей грудки, купленной в какой-то из походов в магазин.

Например, если у Окорочка будет два похода в магазин, в первый поход он купит 200 граммов риса и 500 граммов куриной грудки, а во второй — 100 граммов риса и 200 граммов куриной грудки, то он сможет приготовить только 2 приёма пищи с $$$k = 400$$$ — например, так:

• первый приём пищи: 100 граммов риса и 300 граммов куриной грудки с первого похода;
• второй приём пищи: 200 оставшихся граммов куриной грудки с первого похода и 200 граммов куриной грудки со второго похода.

Помогите Окорочку определить максимальное количество приёмов пищи, которые он сможет приготовить для себя до осени!

Петя и Вася играют в игру. У них есть три кучки камней размера $$$n_1$$$, $$$n_2$$$, и $$$n_3$$$ соответственно. За ход разрешается взять из одной любой кучки ровно $$$a_1$$$, $$$a_2$$$, $$$\ldots$$$, $$$a_{k - 1}$$$ или $$$a_k$$$ камней. Петя и Вася по очереди берут камни, начинает Петя. Проигрывает тот, кто не может сделать свой ход. Определите имя того, кто победит.

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

Рассмотрим все пути из листьев в корень; здесь листом считается вершина, у которой нет сыновей. Для каждого пути посчитаем сумму $$$k$$$ максимальных чисел, встречающихся в его вершинах — или всех этих чисел, если в пути меньше $$$k$$$ вершин. Найдите максимальную такую сумму.