Динамическое программирование

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

Сегодня рабочий день системного администратора Миши начался со звонка секретаря Тани, которая в очередной раз не справилась с редактированием документа. Миша моментально пришёл к Тане и узнал, что в результате ошибки в папке на ее компьютере оказалось n копий документа, над которым она сейчас работает. Других документов в папке нет. Таня просит Мишу удалить лишние копии, чтобы у неё осталась ровно одна копия нужного файла.

Таня работает в операционной системе Bububuntu, в которой есть две команды, позволяющие удалять файлы. Первая команда удаляет один произвольный файл с компьютера. На выполнение этой команды Миша тратит A секунд. Вторая команда рассчитана как раз на случай, подобный Таниному, и позволяет уменьшить количество копий файла в k раз. В силу технический особенностей Bububuntu эта команда работает, только если количество файлов в папке делится на k без остатка. На выполнение этой команды Миша тратит B секунд.

Для решения Таниной проблемы Миша решил по очереди использовать эти команды таким образом, чтобы в конце в папке остался ровно один документ.

У Миши сегодня много других дел, поэтому он хочет справиться с проблемой как можно быстрее. Помогите Мише и скажите, за какое минимальное количество секунд он сможет решить Танину проблему, если будет действовать оптимально.

 

Входные данные

В первой строке содержится целое число n ( 1 <= n <= 2*10⁹ ) - количество копий документа в папке у Тани. 
Во второй строке содержится целое число k ( 1 <= k <= 2*10⁹ ) - количество раз, в которое уменьшает количество файлов вторая команда.
В третьей строке содержится целое число A ( 1 <= A <= 2*10⁹ ) - количество секунд, которое Миша тратит на выполнение первой команды.
В четвёртой строке содержится целое число B ( 1 <= B <= 2*10⁹ ) - количество секунд, которое Миша тратит на выполнение второй команды.

 

Выходные данные

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

 

Примечание

В первом тестовом примере оптимальная стратегия Миши такова:

• За 3 секудны удалить один файл, в результате чего в папке останется 8 файлов. Обратите внимание, что Миша не мог использовать вторую команду, потому что 9 не делится на 2 .
• За 1 секунду уменьшить число файлов в 2 раза. После этой операции в папке останется 4 файла.
• За 1 секунду уменьшить число файлов в 2 раза. После этой операции в папке останется 2 файла.
• За 1 секунду уменьшить число файлов в 2 раза. После этого в папке останется 1 файл и цель Миши будет выполнена.

На выполнение этих четырёх операций Миша потратит 6 секунд. Можно показать, что Миша не сможет удалить лишние файлы меньше, чем за 6 секунд.

Во втором тестовом примере Мише выгодно 4 раза удалить один файл. Так как на одно удаление Миша тратит 2 секунды, на выполнение всего задания Миша потратит 4·2 = 8 секунд. Кроме того, Миша мог бы удалить лишние файлы, один раз воспользовавшись второй командой, но, так как её выполнение занимает 20 секунд, Мише это не выгодно.
 

 

Примеры

№	Входные данные	Выходные данные
1	9 2 3 1	6
2	5 5 2 20	8
3	19 3 4 2	12

Дана последовательность из N целых чисел. Рассматриваются все её непрерывные подпоследовательности. Найдите среди них подпоследовательность с максимальной суммой, определите её длину. В ответе укажите количество элементов в этой подпоследовательности.

Для борьбы с могучими рейнджерами Рита Репульса и Лорд Зедд решили объединить Глиняный и Зедд патрули. Для более эффективного нападения на Энджел Гроув они хотят построить свою армию в две шеренги. Количество солдат в первой шеренге равно количеству солдат во второй.
Рита любит два вопроса:

•  «Правда ли, что ровно x из твоих соседей из Зедд патруля?»
•  «Правда ли, что ровно y из твоих соседей из Глиняного патруля?»

Соседями в данном построении являются солдаты слева и справа в той же шеренге, а также солдат, который стоит на той же позиции, но в другой шеренге. Рита выбрала либо один из этих вопросов либо оба, и задала каждому солдату. Всем солдатам были заданы вопросы с одними и теми же значениями x и/или y.
Зордан с помощью своей магической силы все это время наблюдал за процессом построения. Он был очень удивлен тем, что ответы всех солдат были положительными. Однако, он помнит, что солдаты из Зедд патруля всегда говорят правду, а солдаты из Глиняного патруля обязательно солгут хотя бы на один вопрос.
Так как солдаты из Зедд патруля наиболее опасны по мнению Зордана, исходя из ответов, он хочет узнать какое наименьшее и наибольшее количество солдат из Зедд патруля могло быть в объединенной армии. Он обратился к вам за помощью!

Входные данные
В единственной строке входного файла содержатся три целых числа k, x, y — количество солдат в одной шеренге и числа из вопросов (1 ≤ k ≤ 10⁵; -1 ≤ x, y ≤ 3).
Если x = -1, это означает, что Рита не задавала первый вопрос.
Если y = -1, это означает, что Рита не задавала второй вопрос.
Гарантируется, что Рита задала хотя бы один вопрос.

Выходные данные
Если для данных k, x и y не существует ни одного способа построения, выведите -1.
Иначе, первая строка выходного файла должна содержать одно число — наименьшее возможное количество солдат из Зедд патруля в армии.
В следующих двух строках должно содержаться по k символов «0» и «1» — описание шеренг:

•  «0» означает, что в построении на соответствующей позиции стоит солдат из Глиняного патруля.
•  «1» — солдат из Зедд патруля.

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

Примеры

№	Входные данные	Выходные данные
1	2 0 -1	2 01 10 2 01 10
2	5 1 2	0 00000 00000 4 01010 01010
3	1 2 2	0 0 0 0 0 0
4	10 0 3	5 0100010010 0001000100 8 0101010100 0010101010

Для биномиальных коэффициентов (числа сочетаний из n по k) хорошо известна рекуррентная формула: \(C^k_n=C^{k-1}_{n-1}+C^{k}_{n-1}\), \(C^0_n = C^n_n=1\).
Входные данные
Вводится 2 числа - n и k.

Выходные данные
Необходимо вывести  значение  \(С^k_n\) .
 

Примеры

№	Входные данные	Выходные данные
1	4 2	6

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


Входные данные
Вводятся два числа N и M - размеры таблицы (1<=N<=10, 1<=M<=10).

Выходные данные
Выведите искомое количество вариантов.
 

Примеры

№	Входные данные	Выходные данные
1	2 3	3

 

У Громозеки N печенек. На i-й (1<=i<=N) печеньке написано целое число xi. Он выбирает одну или несколько из этих печенек, так чтобы среднее значение целых чисел, записанных на выбранных печеньках, было равно А.
Какими способами он может сделать свой выбор?

Входные данные
В первой строке вводятся два целых числа N (1<=N<=50) и A (1<=A<=50). Во второй строке N целых чисел - xi (1<=xi<=50).

Выходные данные
Выведите одно число - количество способов выбрать такие печеньки, чтобы среднее значение всех записанных чисел на печеньках было ровно A.
 

 

Примеры

№	Входные данные	Выходные данные	Примечение
1	4 8 7 9 8 9	5	Ниже приведены 5 способов выбрать печеньки так, чтобы в среднем было 8. 1) Выберите 3-ю печеньку. 2) Выберите 1-ю и 2-ю печеньки. 3) Выберите 1-ю и 4-ю печеньки. 4) Выберите 1-ю, 2-ю и 3-ю печеньки. 5) Выберите 1-ю, 3-ю и 4-ю печеньки.
2	3 8 6 6 9	0
3	8 5 3 6 2 8 7 6 5 9	19
4	33 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3	8589934591	Ответ может не соответствовать 32-битному целому числу.

 

Со времен написания условия предыдущей задачи многое изменилось. Симпатичные узоры (о том, что это такое – см. задачу "Симпатичные узоры") стали очень популярны по всему миру, поэтому люди готовы содержать очень большой участок земли, лишь бы иметь на ней узор, не встречающийся больше нигде.

Теперь компания BrokenTiles является ведущим производителем симпатичных узоров в мире! Для составления плана исполнительному директору Васе по-прежнему необходимо знать, сколько клиентов могут рассчитывать на узор данных размеров.

Так как масштабы буквально мировые, N <= 10¹⁰⁰. Однако Вася не любит большие числа, поэтому просит выдать ответ по модулю P.

Входные данные
В первой строке входных данных  содержатся три положительных целых числа, разделенные пробелом – N, M и P (1 <= N <= 10¹⁰⁰, 1 <= M <= 5, 1 <= P <= 10 000).

Выходные данные
Выведите  количество различных симпатичных узоров N x M по модулю P .

Чтобы затруднить снятие денег, банк на планете Крокрыс разрешает своим клиентам снимать только одну из следующих сумм за одну операцию:
- 1 крокрыскоин (действующая монета на планете Крокрыс);
- 6 крокрыскоинов, 36 (=6²) крокрыскоинов, 216(=6³) крокрыскоинов , ...;
- 9 крокрыскоинов, 81 (=9²) крокрыскоинов, 729(=9³) крокрыскоинов , ...
Сколько минимум операций требуется, чтобы вывести ровно N крокрыскоинов?
Невозможно повторно внести снятые вами деньги.

Входные данные
На вход подается целое число N (\(1<=N<=100000\)).

Выходные данные
Выведите ответ на задачу.

 

Примеры

№	Входные данные	Выходные данные	Пояснения
1	127	4	При снятии 1 + 9 + 36 + 81 получится снять 127 крокрыскоина за 4 операции.
2	3	3	1+1+1 = 3, всего 3 операции
3	44852	16

 

У нас есть сетка с H строками и W столбцами. Квадрат в i-й строке и j-м столбце будет называться Square(i, j). Целые числа от 1 до H·W записаны по всей сетке, а целое число, записанное в Square(i, j), равно Ai,j.
Вы - волшебник (волшебница), и можете телепортировать фигуру, помещенную на Square(i, j) в Square(x, y), потратив \(|x-i|+|y-j|\) маджиков (магических монет).
Теперь вам нужно пройти Q практических тестов на свои способности как волшебника (волшебницы). I-е испытание будет проводиться следующим образом:
- первоначально фигура располагается в квадрате, где записано целое число Li;
- пусть x будет целым числом, записанным в квадрате, занятом фигурой. Неоднократно переместите фигуру в квадрат, где написано целое число x+D, пока x не станет равен Ri. Тест заканчивается, когда x = Ri .
Гарантируется, что Ri- Li делится на D.
Для каждого теста найдите сумму маджиков, израсходованных во время этого теста.

Входные данные
В первой строке заданы три целых числа: H, W и D (\(1\leq H,W \leq 300\), \(1 \leq D \leq H \cdot W\)).
В следующих H строках записано по W чисел Ai,j (\(1 \leq A_{i,j} \leq H \cdot W\), \(A_{i,j} \neq A_{x,y} ((i,j) \neq (x,y))\).
В следующей строке записано целое число Q (\(1 \leq Q \leq 10^5\)).
В последних Q строках записано по 2 целых числа: Li и Ri (\(1 \leq L_i \leq R_i \leq H \cdot W\)), \((R_i-L_i)\) кратно D.

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

 

Примеры

№	Входные данные	Выходные данные	Пояснения
1	3 3 2 1 4 3 2 5 7 8 9 6 1 4 8	5	- 4 записано Square (1,2). - 6 записано в Square (3,3). - 8 записано in Square (3,1). Таким образом, сумма магических очков, израсходованных во время одного теста, составляет:  \((|3-1|+|3-2|)+(|3-3|+|1-3|)=5\).
2	4 2 3 3 7 1 4 5 2 6 8 2 2 2 2 2	0 0	Обратите внимание, что может быть тест, в котором фигура вообще не перемещается, и может быть несколько идентичных тестов.
3	5 5 4 13 25 7 15 17 16 22 20 2 9 14 11 12 1 19 10 6 23 8 18 3 21 5 24 4 3 13 13 2 10 13 13	0 5 0

 

Рассмотрим фигуру, аналогичную показанной на рисунке (большой равносторонний треугольник, составленный из маленьких равносторонних треугольников). На рисунке приведена фигура, состоящая из 4-х уровней треугольников.



Напишите программу, которая будет определять, сколько всего в ней треугольников (необходимо учитывать не только "маленькие" треугольники, а вообще все треугольники — в частности, треугольник, выделенный жирным, а также вся фигура, являются интересующими нас треугольниками).

Входные данные
Вводится одно число N — количество уровней в фигуре (1 ≤ N ≤ 100000).

Выходные данные
Выведите  количество треугольников в такой фигуре.

Примеры

№	Входные данные	Выходные данные
1	1	1
2	2	5
3	4	27

Вновь открытое казино предложило оригинальную игру.

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

Рассмотрим пример. Пусть на столе выставлен ряд фишек rrrgggbbb, и крупье объявил последовательности rg и gb. Игрок, например, может забрать фишки rg, лежащие на третьем и четвёртом местах слева. После этого крупье сдвинет фишки, и на столе получится ряд rrggbbb. Ещё дважды забрав фишки rg, игрок добьётся того, что на столе останутся фишки bbb и игра закончится, так как игроку больше нечего забрать со стола. Игрок мог бы действовать и по-другому — на втором и третьем ходах забрать не последовательности rg, а последовательности gb. Тогда на столе остались бы фишки rrb. Аналогично, игрок мог бы добиться того, чтобы в конце остались ряды rrr или rbb.

После окончания игры полученные фишки игрок меняет на деньги. Цена фишки зависит от её цвета.

Требуется написать программу, определяющую максимальную сумму, которую сможет получить игрок.

Входные данные
В первой строке входных данных содержится число K (1 ≤ K ≤ 26) — количество цветов фишек. Каждая из следующих K строк начинается со строчной латинской буквы, обозначающей цвет. Далее в той же строке через пробел следует целое число X_i (1 ≤ X_i ≤ 150, i = 1..K) — цена фишки соответствующего цвета.

В (K+2)-ой строке описан ряд фишек, лежащих на столе в начале игры. Ряд задаетсяL строчными латинскими буквами (1 ≤ L ≤ 150), которые обозначают цвета фишек ряда.

В следующей строке содержится число N(1 ≤ N ≤ 150) — количество последовательностей, которые были объявлены крупье. В следующих N строках записаны эти последовательности. Гарантируется, что сумма длин этих N строк не превосходит 150 символов, и все они непустые.

Выходные данные
Выведите единственное целое число — максимальную сумму денег, которую может получить игрок.
 

Примеры

№	Входные данные	Выходные данные
1	3 v 3 l 1 u 2 luvu 3 luv vul uuu	6

Группа школьников решила сходить в поход вдоль Москвы-реки. У Москвы-реки существует множество притоков, которые могут впадать в нее как с правого, так и с левого берега.

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

Школьники заранее изучили карту и записали, в какой последовательности в Москву-реку впадают притоки на всем их маршруте.

Помогите школьникам по данному описанию притоков определить минимальное количество переправ, которое им придется совершить во время похода.

Входные данные
Единственная строка содержит описание Москвы-реки между начальной и конечной точкой похода. Длина строки не превосходит 10⁵ символов.

Каждый символ строки может быть одной из трех латинских букв L, R или B. Буква L означает, что очередной приток впадает в реку с левого берега, R - приток впадает в реку с правого берега и B - притоки впадают с обоих берегов реки в одном месте. Поход начинается на левом берегу перед описанной частью реки и заканчивается на правом берегу после описанной части.

Выходные данные
Выведите одно целое число - минимальное количество переправ.

Примечания
Рисунок к приведенному ниже примеру.

Примеры

№	Входные данные	Выходные данные
1	LLBLRRBRL	5

Вам дано положительное целое число N (\(1<=N<=10^{18}\)). Найдите количество пар целых чисел u и v (\(0<=u, v<=N\)) таких, что существуют два неотрицательных целых числа a и b, удовлетворяющих \(a\ xor\ b=u\) и \(a+b=v\). Здесь xor обозначает побитовое исключающее ИЛИ. Поскольку ответ может быть очень большим, вычислите его по модулю \(10^9+7\).

Входные данные
На вход подается положительное целое число N (\(1<=N<=10^{18}\)).

Выходные данные
Выведите количество возможных пар целых чисел u и v (\(0<=u, v<=N\)) , по модулю \(10^9+7\).
 

 

Примеры

№	Входные данные	Выходные данные	Пояснения
1	3	5	u=0,v=0 (Пусть a=0,b=0, тогда 0 xor 0=0, 0+0=0) u=0,v=2 (Пусть a=1,b=1, тогда 1 xor 1=0, 1+1=2) u=1,v=1 (Пусть a=1,b=0, тогда 1 xor 0=1, 1+0=1) u=2,v=2 (Пусть a=2,b=0, тогда 2 xor 0=2, 2+0=2) u=3,v=3 (Пусть a=3,b=0, тогда 3 xor 0=3, 3+0=3)
2	1422	52277
3	1000000000000000000	787014179

 

Скажем, что последовательность строк t₁ , ..., t_k является путешествием длины k , если для всех i > 1 t_i является подстрокой t_{i - 1} строго меньшей длины. Например, { ab , b } является путешествием, а { ab , c } или { a , a } — нет.

Определим путешествие по строке s как путешествие t₁ , ..., t_k , все строки которого могут быть вложены в s так, чтобы существовали (возможно, пустые) строки u₁ , ..., u_{k + 1} , такие, что s = u₁t₁u₂ t₂ ... u_k t_k u_{k + 1} . К примеру, { ab , b } является путешествием по строке для abb , но не для bab , так как соответствующие подстроки расположены справа налево.

Назовём длиной путешествия количество строк, из которых оно состоит. Определите максимально возможную длину путешествия по заданной строке s .

Входные данные
В первой строке задано целое число n ( 1 ≤ n ≤ 500 000 ) — длина строки s .

Во второй строке содержится строка s , состоящая из n строчных английских букв.

Выходные данные
Выведите одно число — наибольшую длину путешествия по строке s .

Примечание
В первом примере путешествием по строке наибольшей длины является { abcd , bc , c } .

Во втором примере подходящим вариантом будет { bb , b } .

Примеры

№	Входные данные	Выходные данные
1	7 abcdbcc	3
2	4 bbcb	2

У вас есть таблица c N строками и M столбцами. В каждой ячейке таблицы записана одна строчная буква английского алфавита. Рассмотрим все возможные пути от левого верхнего угла до правого нижнего угла, если вам разрешено идти только вправо и вниз. Конкатенация букв в порядке обхода составляют строку. Скажем, что эта строка - значение пути. Теперь рассмотрим все такие пути и отсортируем их значения в алфавитном порядке. Ваша задача найти значение K-го пути в этом отсортированном листе.

Входные данные
В первой строке задается два целых числа N - количество рядов и M - количество столбцов заданной таблицы (1 <= N, M <= 30). Каждая из следующих N строк содержит ровно M строчных букв английского алфавита. Последняя строка входного файла содержит целое число K (1 <= K <= 10¹⁸). Гарантируется, что для K ответ всегда существует.

Выходные данные
Выведите ответ на задачу

Пояснения к примеру
abcdgk, abcdgk, abcdjk, abfdgk, abfdjk, abfijk, aefdgk, aefdjk, aefijk, aehijk
 

Примеры

№	Входные данные	Выходные данные
1	3 4 abcd efdg hijk 4	abfdgk

Вы хотите, чтобы небоскребы в вашем городе имели красивый вид. Решено построить N небоскребов в ряд. У небоскреба с номером i должно быть ровно h[i] этажей.

У Вас есть предложения от различных строительных компаний. Первая из них предлагает строить один этаж в любом из небоскребов за 3 миллиона евро. Вторая предлагает строить по одному этажу в каждом из двух соседних небоскребов за 5 миллионов евро. Заметим, что не имеет значения, находятся ли эти этажи на одинаковой высоте или нет. Третья компания предлагает строить по одному этажу в каждом из трех последовательных небоскребах за 7 миллионов евро.

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

Входные данные
Первая строка содержит одно целое число N (1 ≤ N ≤ 300). Вторая строка содержит N целых чисел h[1], h[2] ..., h[N], 1 ≤ h[i] ≤ 200.

Выходные данные
В единственной строке выведите одно целое число: минимальную сумму денег для строительства, в миллионах.

Дана сетка с N + 1 рядами и M + 1 столбцами. Черепаха находится на клетке (0, 0) и хочет попасть в клетку (N, M). Черепаха может идти только вверх или вправо. На сетке в K клетках находятся ловушки. Если черепаха пойдет в одну из этих клеток, то она перевернется. У черепашки есть силы для того, чтобы встать не более чем T раз. Посчитайте, сколькими различными путями черепаха может попасть в клетку (N, M). Так как это число может быть очень большим, выведите остаток от его деления на Z.

Входные данные
В первой строке входного файла задается 5 целых чисел: N, M, K, T и Z (1 ≤ N,M ≤ 300000, 0 ≤ K, T  20, 1 ≤ Z ≤ 10⁹). В каждой из следующих K строк расположены координаты соответствующей клетки с ловушкой X, Y (0 ≤ X ≤ N, 0 ≤ Y ≤ M). Гарантируется, что все клетки с ловушками различные и в клетках (0, 0) и (N, M) ловушек нет.

Выходные данные
Выведите требуемое число.

Примеры

№	Входные данные	Выходные данные
1	1 1 1 0 100 0 1	1
2	2 2 0 0 10	6

В этой задаче, как и в задаче B, Петя снова собирает своего M-лапого Зверя на прогулку (однако количество лап у Зверя в этой задаче может быть до 1000). Снова ему мама оставила N штанов, имеющих соответственно K₁, K₂, …, K_N штанин. Однако тетерь Петя хочет надеть на Зверя штаны так, чтобы выполнялись следующие условия:

• на каждой лапе была надета хотя бы одна штанина (гарантируется, что это всегда возможно),
• количество штанин, надетых на самую «утепленную» лапу, должно как можно меньше отличаться от количества штанин, надетых на самую легко одетую лапу (когда количество штанов, одетых на разные лапы, сильно отличается, Зверь испытывает дискомфорт),
• в отличие от задачи B Петя не обязан надеть на Зверя все имеющиеся штаны — какие-то из них можно оставить дома.

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

Помогите Пете – напишите программу, которая для каждой лапы укажет, сколько штанин должно быть на нее надето.

Входные данные
Вводится сначала число M, а затем число N (1 ≤ M ≤ 1000, 1 ≤ N ≤ 100). Далее вводятся N чисел Ki, обозначающих число штанин у оставленных мамой штанов (1 ≤ K_i ≤ M). Сумма всех Ki не меньше, чем M.

Выходные данные
Выведите M строк, в i-ой строке должно быть выведено количество штанин, надетых на i-ю лапу. Если искомых ответов несколько, то выведите любой из них.
 

Примеры

№	Входные данные	Выходные данные	Пояснение
1	4 3 1 2 3	1 1 1 1	Первые штаны надеты на лапу 1; вторые штаны не используем; третьи штаны надеты на лапы 2, 3 и 4. Таким образом, на всех лапах по 1 штанине.
2	4 2 3 2	2 1 1 1	Первые штаны надеты на лапы 1, 2 и 3; вторые штаны надеты на лапы 1 и 4. Таким образом, количество штанов на самой «утепленной» лапе (это лапа номер 1) – 2, а на остальных лапах по одной штанине, т.е. количество штанин на разных лапах отличается на один. Нетрудно заметить, что в этом примере нельзя одеть зверя так, чтобы на всех лапах было поровну штанин, поэтому этот ответ является оптимальным.

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

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

Напишите программу, которая вычисляет, какое наибольшее количество рублей сможет получить Петя к исходу N-го дня.

Законы изменения курсов устроены так, что в течение указанного периода рублевый эквивалент той суммы, которая может оказаться у Пети, не превысит 10⁸ рублей.

Входные данные
Первая строка входного файла содержит одно число N (1≤N≤5000). В каждой из следующих N строк записано по 2 числа, вычисленных по Петиным законам для соответствующего дня — сколько рублей будет стоить 1 доллар, и сколько рублей будет стоить 1 евро. Все эти значения не меньше 0.01 и не больше 10000. Значения заданы точно и выражаются вещественными числами не более, чем с двумя знаками после десятичной точки.

Выходные данные
В выходной файл выведите искомую величину с точностью не менее двух знаков после десятичной точки.
 

Примеры

№	Входные данные	Выходные данные
1	1 30.00 9999.99	100.00

Вася и Петя играют в следующую игру. Они берут колоду из 36 карточек. На каждой карточке написано число от 1 до 9 и каждая карточка покрашена в один из 4 цветов так, что есть ровно по 9 карточек каждого цвета и они пронумерованы числами от 1 до 9. Карты перемешиваются, и игрокам раздается по 18 карт.

Дальше игроки по очереди делают ходы. За один ход игрок может выложить на стол одну карточку по следующим правилам. Карточку с цифрой 5 можно выкладывать на стол в любой момент. Карточку с другой цифрой можно выкладывать только если на стол уже выложена карточка того же цвета, на которой написано число на 1 большее или на 1 меньшее, чем на данной карточке (не важно, была ли эта карточка выложена вами или вашим противником, и была ли она выложена на предыдущем ходе или раньше). Если игрок может выложить хоть какую-то карточку, он обязан делать ход. Если ни одну карточку игрок выложить не может, он пропускает ход.

Выигрывает тот, кто первым выложит все свои карточки на стол.

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

Входные данные
Во входном файле записаны 18 пар чисел, описывающих карточки, которые достались первому игроку. Каждая карточка описывается двумя числами — номером цвета (от 1 до 4) и цифрой, которая написана на карточке (от 1 до 9). Второму игроку, соответственно, достались все остальные карточки.

Выходные данные
В выходной файл выведите одно число (1 или 2) — номер игрока, который выиграет при оптимальной игре обоих игроков.
 

Примеры

№	Входные данные	Выходные данные
1	1 1 1 2 1 3 1 4 1 5 1 6 1 7 1 8 1 9 2 1 2 2 2 3 2 4 2 5 2 6 2 7 2 8 2 9	1