Джон — фанат сериала «Во все престолы». Совсем скоро выходит новый сезон, и Джон хочет его посмотреть.

Серии будут выходить по одной в день. Джону не хочется скачивать их каждый раз вручную, поэтому он собирается написать программу, которая будет делать это за него. Каждая серия — это отдельный файл, размер файла, содержащего \(i\)-ю серию, равен \(s_i\) байт.

Программа Джона будет действовать следующим образом. Она один за другим будет отправлять на сервер запросы, где \(j\)-й запрос представляет собой «загрузить очередные \(x_j\) байт». В ответ на такой запрос сервер возвращает пакет данных, содержащий очередные \(x_j\) байт файла, а также заголовок, содержащий \(k\) байт различной служебной информации. Таким образом, размер пакета равен \(x_j + k\) байт, при этом значение \(k\) одно и то же для всех запросов.

Когда в результате некоторого запроса скачивается последний байт файла, программа завершает свою работу и не делает дальнейших запросов к серверу. Однако протокол устроен таким образом, что размер пакета равен \(x_j + k\), даже если был достигнут конец файла и в действительности было загружено меньше \(x_j\) байт полезной информации.

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

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

Никита очень любит математические парадоксы. Недавно он заметил, что

\(\)\frac{2}{3} < \frac{1}{1}; \frac{1}{2} < \frac{6}{11},\(\) но при этом если у меньших дробей сложить числители и знаменатели и то же сделать с большими дробями, то получатся дроби

\(\)\frac{2+1}{3+2} = \frac{3}{5}; \frac{1+6}{1+11} = \frac{7}{12},\(\) причем \(\)\frac{3}{5} > \frac{7}{12}.\(\) Тогда Никита выписал в ряд \(k\) дробей и хочет выбрать среди них четыре дроби, чтобы выполнялись неравенства \(\)\frac{m_1}{n_1} \le \frac{m_2}{n_2}; \frac{m_3}{n_3} \le \frac{m_4}{n_4},\(\) а величина \(\)\frac{m_1 + m_3}{n_1 + n_3} - \frac{m_2 + m_4}{n_2 + n_4}\(\) была максимальна. Каждую из записанных дробей можно взять только в качестве одной из выбранных четырех. Помогите Никите решить эту сложную задачу.

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

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

Помогите Диме решить головоломку оптимальным образом.

Например, если у Димы есть фигура и препятствие, показанные на рисунке ниже, выгоднее всего уронить фигуру следующим образом:

В Байтландии решили провести шоу «Кто хочет стать миллионером?». Участнику шоу по очереди задаются \(n\) вопросов, если он ответил на \(i\)-й вопрос, его приз становится равным \(a_i\) . После любого вопроса участник шоу может забрать свой приз и покинуть шоу.

Организаторы шоу решили, что число вопросов будет равно \(n\), но не могут определиться с призами. Первый вопрос обычно очень простой и за него решено было установить приз равный \(a_1 = 100\) битов. Каждый следующий вопрос сложнее, поэтому очередной приз должен быть хотя бы вдвое больше предыдущего. Наконец, призы должны быть достаточно круглыми.

Организаторы называют сумму достаточно круглой, если нули в конце этой суммы составляют хотя бы половину цифр в записи этой суммы. Они решили, что в качестве приза \(a_i\) для всех \(i > 1\) они выберут минимальное достаточно круглое число, хотя бы в 2 раза большее \(a_{i−1}\). Помогите организаторам понять, чему будут равны призы.

Больше всего Генерал Петров любит строевую подготовку. Однажды в построении участвовало \(n\) солдат, для простоты пронумерованных от 1 до \(n\). Солдаты выстроились в ряд, при этом на месте \(i\) стоял солдат с номером \(a_i\) . После этого адъютант генерала прошёл вдоль строя и проверил, что перестановка в точности совпадает с придуманной генералом.

Некоторое время спустя генерал захотел снова расставить солдат в том же порядке. Однако он забыл, как именно он расставил солдат в тот раз. К счастью, у адъютанта генерала хорошая память — про \(m\) пар позиций \(x_i , y_i\) он помнит, что номер солдата, стоявшего на месте \(x_i\) , меньше номера солдата, стоявшего на месте \(y_i\) .

Адъютант стал по очереди сообщать генералу пары \(x_i , y_i\) . Но генерал хочет побыстрее начать строить солдат. Помогите ему определить такое минимальное \(k\), что как только адъютант сообщит ему первые \(k пар позиций, генерал сможет однозначно определить искомую перестановку.