Вечер. Трактир «Адмирал Бенбоу». Полумрак. Билли Бонс сидит у камина, попивая ром и разглядывая обратную сторону карты сокровищ. Там написано натуральное число $$$x$$$.

С помощью этого числа можно узнать количество монет, спрятанных на острове. Для этого нужно найти минимальное число, большее $$$x$$$, которое удовлетворяет следующему условию: любая цифра из этого числа должна отличаться от цифры, которая находится в том же разряде числа $$$x$$$. Например, если $$$x = 13$$$, то число 18 не удовлетворяет упомянутому условию, так как у этих двух чисел совпадает первая цифра.

Помогите Билли Бонсу найти количество монет в сундуке. В награду он поделится с вами сокровищами.

Картинка к первому примеру.

Доктор Ливси собирается в экспедицию за сокровищами. Так как он единственный доктор в команде, он первым делом хочет собрать необходимые медикаменты. У доктора есть много шприцов. Каждый шприц представляет собой прямоугольник $$$1\times k$$$. А также есть большая коллекция сумок, одну из которых он хочет взять с собой. В его коллекции есть сумки всех возможных размеров $$$x\times y$$$, где $$$1 \le x, y \le n$$$. При этом Доктор Ливси хочет взять такую сумку, что в нее можно будет положить шприцы на дно сумки параллельно ее сторонам одним слоем без пересечений так, чтобы дно сумки было полностью покрыто. Дно сумки размера $$$x\times y$$$ представляет собой прямоугольник размера $$$x\times y$$$. Шприцы можно располагать как горизонтально, так и вертикально. Помогите Доктору Ливси понять, сколько сумок из его коллекции подходят для экспедиции.

В трактир «Адмирал Бенбоу» привезли новую партию рома — всего $$$2^{n} - 1$$$ бутылок, и каждая из них имеет свой номер от 1 до $$$2^{n} - 1$$$. Кроме того, в трактире есть $$$2^{n} - 1$$$ коробок, также пронумерованных от $$$1$$$ до $$$2^{n} - 1$$$.

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

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

Доктор Ливси заботится не только о физическом, но и о психологическом состоянии команды. Чтобы экипаж чувствовал себя счастливее, доктор решил снизить уровень негатива. На корабле находится $$$n$$$ человек, и настроение каждого можно описать целым числом $$$a_i$$$.

Доктор Ливси пока не обладает достаточным опытом, поэтому он может улучшить настроение только одной группе людей. Выбрав подотрезок людей, доктор изменяет их настроение на противоположное. Формально это означает, что он выбирает два числа $$$1 \le l \le r \le n$$$ и меняет знаки всех значений $$$a_i$$$ на отрезке $$$[l; r]$$$.

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

Джон Сильвер с командой пиратов во время поиска места, где зарыты сокровища, наткнулись на очередную загадку Флинта. На карте написано, что им нужно пройти $$$d$$$ шагов на север, чтобы прийти на место, где спрятан клад. Однако само число $$$d$$$ пиратам неизвестно, сказано лишь то, что это было любимое число капитана Флинта.

Джон Сильвер долго плавал с капитаном Флинтом и очень хорошо его знал. Каждый раз, когда капитан пересчитывал свои богатства, он высыпал все золотые монеты на стол и складывал их в кучки по $$$d$$$, чтобы было удобнее считать. Все лишние монеты, которых не хватало для очередной кучки, он раздавал команде. Именно из-за частого подсчета денег число $$$d$$$ и стало любимым для Флинта.

В день, когда Флинт с командой прибыли на остров, прежде чем спрятать сокровища, капитан, как обычно, решил их пересчитать. Затем взял $$$n$$$ сундуков и начал складывать в них деньги. Он по очереди брал со стола кучку из $$$d$$$ монет и клал ее всю в один из сундуков. Однако, когда на столе осталась всего одна кучка монет, внезапно несколько членов команды напали на Флинта с целью забрать все сокровища себе. Разумеется, они недооценили опыт капитана и сами пали в бою с ним. Флинт же осознал, что нужно торопиться, в спешке собрал оставшиеся монеты со стола и бросил их в 2 ближайших к нему сундука, не обращая внимания, сколько монет из кучки оказалось в каждом из них. Схватив свои сокровища, он отправился их закапывать.

Все это Джон Сильвер видел своими глазами, но пойти за Флинтом и узнать, где он хочет спрятать деньги, было опасно. Зато Сильвер смог запомнить, сколько монет было в каждом сундуке. Но он тогда не знал, что самой ценной информацией в тот момент было именно число $$$d$$$ — размер кучек с монетами. И теперь Джон никак не может его вспомнить. Помогите ему определить наибольшее возможное число $$$d$$$, зная, сколько монет было в каждом сундуке.

На таинственном острове капитан Флинт оставил карту сокровищ, на которой записаны подсказки в виде последовательности чисел — массив $$$a$$$. У пиратов есть стартовое значение $$$x$$$, которое им нужно преобразовать, следуя всем шагам на карте, чтобы добраться до сокровища.

Для каждого значения $$$x$$$, которое они выбирают, пираты идут по массиву $$$a$$$ от начала до конца и выполняют следующие действия для каждого элемента массива:

1. Если текущее значение $$$x \lt 0$$$, они добавляют к $$$x$$$ текущий элемент массива.
2. Если же $$$x \ge 0$$$, они вычитают из $$$x$$$ текущий элемент массива.

Таким образом, в конце маршрута значение $$$x$$$ становится новым числом, указывающим на местоположение клада.

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

Капитан Смоллетт находится в форте с координатами $$$(0, 0)$$$. Из форта торчат $$$n$$$ ружей, обозначенных векторами $$$(x_i, y_i)$$$. Неподалёку в точке с координатами $$$(a, b)$$$ находится Джон Сильвер, который является кругом радиуса $$$r$$$.

Капитан Смоллетт по своему усмотрению повернёт форт на некоторый угол $$$\alpha$$$ ($$$0^{\circ} \leq \alpha \lt 360^{\circ}$$$) против часовой стрелки, вместе с фортом повернутся все ружья. Затем он $$$k$$$ раз выстрелит из какого-то ружья, выбрав его равновероятно. Во время каждого выстрела ружьё выбирается независимо от всех предыдущих выстрелов, ружья могут повторяться. Джон Сильвер будет убит, если хотя бы один выстрел попадёт в него. Попадания в границу круга тоже считаются.

Капитана волнуют $$$q$$$ вопросов. Вопрос номер $$$i$$$ звучит так: на какой наименьший угол $$$\alpha_i$$$ нужно повернуть форт, чтобы поразить Джона Сильвера с вероятностью хотя бы $$$p_i$$$.

Найдите ответы на все вопросы капитана.

Испаньола наконец-то приблизилась к Острову Сокровищ! Шлюпка пиратов уже отправилась в сторону острова и отплыла от корабля на $$$D$$$ футов. Шлюпка Джима только что спустилась на воду и находится в одной точке с кораблём.

Следующие $$$n$$$ секунд обе лодки будут двигаться прямолинейно в сторону острова. Джим точно знает, что в секунду номер $$$i$$$ шлюпка пиратов сдвинется в сторону острова на $$$b_i$$$ футов. При этом шлюпка Джима в секунду номер $$$i$$$ может сдвинуться в сторону острова на любое целое число футов от $$$0$$$ до $$$a_i$$$ по усмотрению Джима. Считайте, что в течение каждой секунды обе лодки движутся равномерно.

Джим хочет обогнать шлюпку пиратов как можно раньше так, чтобы после этого пираты никогда не догнали Джима. Формально, пусть $$$t$$$ ($$$1 \leq t \leq n$$$) — наименьший номер секунды, такой, что в её конце шлюпка Джима была строго ближе к острову, чем шлюпка пиратов. Джим хочет, чтобы начиная с этого момента и вплоть до конца $$$n$$$-й секунды его шлюпка была строго ближе к острову, чем шлюпка пиратов. Из всех возможных $$$t$$$ он хочет выбрать наименьшее.

Однако Джим точно не знает, чему равно расстояние $$$D$$$. У него есть $$$q$$$ предположений $$$d_1, d_2, \ldots, d_q$$$ чему равно $$$D$$$. Он хочет знать наименьшее возможное число $$$t$$$ для каждого своего предположения.

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

В пиратском мире существует $$$n$$$ островов с сокровищами. Остров под номером $$$i$$$ хранит сундук с $$$a_i$$$ пиастрами. Между островами существует $$$m$$$ морских путей, которые позволяют перемещаться между ними. Острова и пути образуют неориентированный граф, где каждый морской путь соединяет два различных острова.

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

В начале Слепой Пью и его команда находятся на острове с номером 1, где они уже нашли сундук с $$$a_1$$$ пиастрами. Пираты могут начать любое путешествие с текущего острова, но останавливаются только на последнем острове путешествия и открывают сундук там (сундуки промежуточных островов остаются нетронутыми). Все золото Пью забирает к себе в карман. Каждое новое путешествие начинается с острова, на котором закончилось предыдущее.

Каждое путешествие требует оплаты команде. Если длина путешествия равна $$$i$$$, то команда потребует $$$b_i$$$ пиастров за него. Пью выплачивает команде единовременно всю сумму за все путешествия в конце последнего. Если Пью и его команда не совершают ни одного путешествия, то Пью не платит своей команде ничего.

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

Пиастры. Фото в цвете.

Экспедиция за сокровищами началась, но Капитану Смолетту ничего не нравится. Особенно матросы.

Всего на борту есть $$$n$$$ матросов, у каждого из них есть своя роль. Роль $$$i$$$-го матроса описывается натуральным числом $$$a_i$$$. Экспедиция будет длиться $$$q$$$ дней, и в начале каждого дня Капитан Смолетт собирается менять роль ровно одного матроса. После этого, к концу дня капитан Смолетт оценивает свою команду и решает, какая из ролей самая важная, но делает он это не совсем обычным образом.

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

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

Дано $$$n$$$ островов. Известно, что пираты могут перемещаться напрямую только между $$$m$$$ парами островов (это обусловлено особенностями рельефа — корабль с большим количеством сокровищ в некоторых местах может сесть на дно), при этом известно, что $$$m \lt n$$$. Вот только с годами капитан Флинт стал совсем забывчив и не помнит, между какими именно парами островов мог передвигаться его грозный корабль. Но вот что капитан Флинт помнит — так это то, что для каждой пары островов существовало не более 1 пути, по которому можно добраться от первого острова до второго (иными словами, в графе, в котором вершины — это острова, а рёбра — возможные прямые перемещения между островами, нет циклов).

Так как плавать от одного острова к другому — недешёвое удовольствие, то гроза всех морей хочет оценить минимальное суммарное расстояние между каждой парой островов (если между ними, конечно, существует путь) — пираты хотят как можно меньше средств потратить на топливо, которое уйдёт на поездки между островами. Старина Флинт к этому моменту забыл даже начало условия задачи, поэтому вам придётся помочь тем пиратам, кто ещё хоть что-то помнит, и подсказать им, между какими парами островов им можно перемещаться напрямую, чтобы минимизировать суммарное расстояние между каждой парой островов. Если вы не справитесь, то капитан Флинт вспомнит прошлое и начнёт пальбу по вам, поэтому советуем поторопиться!