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

\(\)\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 пар позиций, генерал сможет однозначно определить искомую перестановку.

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

Отправив несколько сообщений, Джек заметил, что ноутбук, а точнее его клавиатура, работает не так, как он ожидал. В процессе ввода сообщения у ноутбука иногда внезапно срабатывает клавиша «Home», в результате чего курсор ввода перемещается в начало строки. Так, например, если у Джека в процессе ввода строки «irailikeyou» клавиша «Home» сработала после ввода букв «a» и «y», то получится строка «ouilikeyira».

Джек планировал набрать строку \(s\), нажимая по очереди на соответствующие клавиши. Закончив набор, он посмотрел на экран и увидел строку \(t\). Теперь он хочет понять, может ли она быть результатом его ввода, если единственная неисправность его ноутбука — лишние срабатывания клавиши «Home», либо у его ноутбука есть еще проблемы. Помогите Джеку.