Джордан Белфорт вышел из тюрьмы и решил вновь завоевать Уолл-Стрит! UAM — главная организация по добыче древних артефактов — также с нетерпением ждала его возвращения, и потому в тот же день связалась с ним — перед главным умом в мире денег появилась вот такая задача:

По всему миру распространились нумизматы, падкие до редких монет из мира инков. За всё время у UAM накопилось приличное количество этих монет, и теперь UAM хочет отправить каждому своему клиенту эти монеты.

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

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

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

Ему интересно, как много пакетов он может снарядить так, чтобы в каждых двух деньги были разложены по-разному. Он нанял вас, опытных программистов, для написания программы, которая поможет ему выяснить это.

У Белфорта есть бесконечное количество пластиковых пакетов одинакового размера. Их размеры — это $$$N$$$ united-метров в высоту и $$$m$$$ united-метров в ширину. А также у него есть бесконечное количество контейнеров размером $$$1 \times 1$$$ united-метров квадратных.

У UAM есть бесконечное количество долларов, а также UAM хочет, чтобы каждому клиенту было доставлено ровно $$$K$$$ монет. Пачка долларов на момент выхода Белфорта из тюрьмы имеют размер $$$1 \times 2$$$ united-метров квадратных.

Требуется узнать, сколько есть различных способов разложить деньги вплотную в пакете так, чтобы среди них было ровно $$$K$$$ контейнеров с монетами. Раскладывать пачки купюр можно только горизонтально или вертикально. Белфорт утверждает, что пакеты с пустотами невозможно безопасно (для денег, несомненно) вакуумировать, пакет должен быть набит битком, поэтому не допускаются способы, в которых есть пустоты, не занятые деньгами!

Так как людей, которые могут быть пособниками Белфорта, на Земле ограниченное число, требуется посчитать ответ по модулю $$$2^{32}$$$.

Дано неориентированное дерево из $$$n$$$ вершин. Каждой его вершине $$$v$$$ соответствует некоторое значение $$$a_v$$$. Определим стоимость любого его поддерева $$$T$$$ следующим образом: $$$$$$\displaystyle \mathrm{cost}(T) = \mathrm{size}(T) \cdot \sum_{v \in T} a_v\text{,}$$$$$$ где $$$\mathrm{size}(T)$$$ — размер поддерева $$$T$$$.

Из исходного дерева удаляется вершина $$$u$$$ вместе со всеми инцидентными ей рёбрами, в результате чего граф превращается в несколько деревьев.

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

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

Однако у исследователя есть ограничение на количество доступной энергии $$$K$$$ и времени $$$M$$$, чтобы завершить миссию. Необходимо составить оптимальную последовательность посещения объектов, которая максимизирует научную ценность экспедиции, учитывая ограничения на энергию и время.

Дано прямоугольное поле размера $$$m \times n$$$. В левой верхней клетке с координатами $$$(1, 1)$$$ — стартовой — стоит жираф. Он хочет попасть в правую нижнюю клетку с координатами $$$(m, n)$$$ — финишную. Каждой клетке поля соответствует целое число — количество деревьев в ней.

Жираф умеет делать ходы двух видов: на $$$k$$$ клеток вниз и $$$1$$$ клетку вправо; или на $$$k$$$ клеток вправо и $$$1$$$ вниз. Жираф хочет пройти по полю из стартовой клетки в финишную, в конце каждого хода поедая листья на деревьях в клетке, в которую он пришёл. В стартовой клетке он ничего не ест. При этом каждый чётный ход жираф чувствует себя голодным, поэтому съедает $$$3t$$$ листьев, а каждый нечётный ход чувствует себя объевшимся, поэтому съедает только $$$t$$$ листьев, где $$$t$$$ — количество деревьев на клетке. Ходы нумеруются с единицы.

Выясните, какое наибольшее количество листьев жираф может съесть в своём путешествии.

Пете подарили необычные кубики: каждый кубик имеет 26 граней, на которых написаны все 26 маленьких букв английского алфавита — по одной букве на каждой грани. Петя захотел сыграть в игру: изначально он выложил $$$n$$$ кубиков в ряд, составив некоторую строку, теперь он хочет превратить её в свою любимую строку. Для этого Петя делает ходы: за один ход Петя может перевернуть один любой кубик, поменяв соответствующую букву строки на любую другую. Также у Пети есть большой пушистый Кот, который может делать ходы вместо Пети. В зависимости от настроения Кот может помочь Пете и за один ход сразу перевернуть кубики так, чтобы получилась любимая Петина строка, или Кот может сделать наоборот — перевернуть кубики так, чтобы получившаяся строка отличалась от любимой Петиной строки в каждой букве. Ход любого игрока возможен, только если он хоть как-то меняет строку из кубиков. Игроки могут делать ходы в любом порядке.

Так как Пете нужно делать доклад по физкультуре, в игре есть время всего лишь на $$$m$$$ ходов. Пете интересно, сколько различных игр может произойти, если после ровно $$$m$$$ ходов должна получиться его любимая строка. Так как число игр может быть очень большим, Пете интересен лишь остаток от деления этого числа на $$$9! = 362\,880$$$. Помогите Пете найти это значение.

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

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

Правила лотереи, как всегда, просты. Участник покупает лотерейный билет, на котором написаны $$$n$$$ положительных целых чисел. Затем в определённый день оглашаются $$$n$$$ положительных целых чисел — выигрышные номера. Все участники их увидят как массив целых чисел $$$b$$$. Также заранее оглашаются призы: если $$$i$$$-й элемент билета участника совпадает с $$$i$$$-м элементом выигрышного билета, участник получает $$$c_i$$$ монет.

Лёлик решил использовать лазейку в системе для своего обогащения. У него есть официальный шаблон лотерейного билета, который представляет собой массив $$$a$$$ размера $$$n$$$, заполненный единицами. Также у Лёлика есть аппарат для изменения цифр на билете.

К сожалению, аппарат самодельный, и работает следующим образом. Лёлик может выбрать два целых числа $$$i$$$ ($$$1 \leq i \leq n$$$) и $$$z$$$ ($$$z \gt 0$$$) и увеличить $$$a_i$$$ на $$$\left\lfloor \frac{a_i}{z} \right\rfloor$$$ (частное от деления $$$a_i$$$ на $$$z$$$, округлённое вниз). Лёлик может выбирать одно и то же $$$i$$$ для операций сколько угодно раз.

Но этот процесс не быстрый, а время лазейки ограничено. Всего Лёлик сможет совершить не более $$$k$$$ операций. Поэтому он попросил вас максимизировать свой выигрыш.

Ваша задача — определить максимальное количество монет, которое может получить Лёлик за не более чем $$$k$$$ операций.

В Институте Морской Биологии открыли несколько новых видов глубоководных моллюсков, и теперь стараются понять их генеалогию. Для этого лаборант Петя извлёк некоторый конкретный участок генома у каждого вида моллюсков, а лаборант Вася построил $$$T$$$ предположительных частичных эволюционных деревьев на основе внешних признаков.

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

Для каждого вида учёные наблюдают один и тот же участок генома, который представляется в виде строки из символов A, G, C и T (каждый символ отображает один нуклеотид). Известно, что у всех видов этот участок имеет одну и ту же длину, но в процессе эволюции некоторые нуклеотиды могли замениться на другие (удалений и добавлений нуклеотидов без замены произойти не могло). При этом каждому из современных видов соответствует один из $$$G$$$ участков генома, извлечённых Петей, а участки генома видов-прародителей неизвестны.

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

Сами лаборанты не смогли решить такую задачу, поэтому просят Вас помочь им!

Даны последовательность различных целых чисел и множество разрешённых разностей. Необходимо найти длину самой длинной возрастающей подпоследовательности, в которой разность между любыми двумя соседними элементами — разрешённая. Например, если разрешённые разности равны $$$1$$$ и $$$3$$$, то подпоследовательность $$$1, 4, 5, 8$$$ будет удовлетворять условию, а последовательность $$$1, 2, 4$$$ — нет, так как разность второго и третьего элемента равна $$$2$$$.

Дано неориентированное дерево из $$$n$$$ вершин. Найдите сумму длин всех простых путей в нём.

Длина простого пути между вершинами $$$u$$$ и $$$v$$$ — это минимальное количество рёбер, по которым нужно пройти, чтобы попасть из $$$u$$$ в $$$v$$$.