Рассмотрим один специальный тип двоичных деревьев поиска, который часто называют "декартовым деревом". Напомним, что двоичным деревом поиска называется двоичное дерево, в каждой вершине которого записан некоторый ключ (в этой задаче ключ представляет собой целое число), причем для каждой вершины u выполнены следующие условия: все ключи в левом поддереве u меньше чем ключ в вершине u , а все ключи в правом поддереве - больше. Будем называть двоичное дерево поиска декартовым деревом, если в каждой вершине u помимо основного ключа х _u хранится также вспомогательный ключ y _u , причем для этих ключей выполнено "условие кучи": если v - родитель u , то y _v < y _u . Будем называть множество пар ( x ₁ , y ₁ ), ( х ₂ , y ₂ ), ... ( х _n , у _n ) корректным , если все x _i – различные числа от 1 до n , и то же условие выполнено для y _i . Легко показать, что для любого корректного множества пар существует в точности одно декартово дерево, которое содержит пары из заданного множества в качестве пар ключей. Рассмотрим двоичное дерево T с n вершинами. Ваша задача - найти количество различных корректных множеств пар, таких что их можно расставить в вершинах T . чтобы превратить его в декартово дерево. Например, для дерева, приведенного на рисунке, существует три соответствующих корректных множества пар: {(1, 2), (2, 3), (3, 1), (4, 4)}, {(1, 2), (2, 4), (3, 1), (4, 3)} и {(1, 3), (2, 4), (3, 1), (4, 2)}.

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

Поиск решения можно проводить с помощью двухмерной модели. В этой модели ось Ох расположена на уровне пола, источник света считается точкой с целочисленными координатами ( b _x , b _y ) . Трубы представляют собой окружности. Центр i -й окружности имеет целочисленные координаты ( с _x , c _y ) , радиус r _i также целый. Так как трубы сделаны из твердого материала, окружности не пересекаются. Трубы не отражают и не пропускают свет. Вы должны написать программу, которая найдет непересекающиеся интервалы на оси Ох , которые уже защищены от света благодаря имеющимся трубам.

Андрей Сергеевич работает воспитателем в детском саду. Недавно он придумал новую веселую игру, для участия в которой все дети разбились на n команд. В качестве призов для участников игры Андрей Сергеевич подготовил d конфет.

По итогам игры оказалось, что в команде, занявшей i -е место, ровно x _i участников.

Теперь перед Андреем Сергеевичем стоит непростая задача: надо распределить конфеты. При этом должны выполняться следующие условия:

• Все участники одной команды должны получить поровну конфет: пусть участники команды, занявшей i -е место получат по a _i конфет;
• Каждый ребенок должен получить хотя бы одну конфету: a _i > 0 ;
• Участники команды, занявшей более высокое место, должны получить больше конфет: если i < j , то a _i > a _j
• Все конфеты должны быть распределены: a _{1 x 1} + a _{2 x 2} + ... a _{nx n} = d

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

Однажды в школе учитель рассказал Алле про так называемые строки Фибоначчи. Строки Фибоначчи определяются следующим образом:

• f ₀ = a
• f ₁ = b
• f _n = f _{n −1} f _{n −2} для каждого n ≥ 2 — конкатенация двух предыдущих строк Фибоначчи

Аллу сразу заинтересовал вопрос — какой максимально длинный палиндром встречается в k -й строке Фибоначчи. Помогите Алле решить эту задачу.

В этой задаче Вам требуется найти максимальную по длине подстроку данной строки, такую что каждый символ встречается в ней не более k раз.