Задача A. Очень Легкая Задача

Сегодня утром жюри решило добавить в вариант олимпиады еще одну, Очень Легкую Задачу. Ответственный секретарь Оргкомитета напечатал ее условие в одном экземпляре, и теперь ему нужно до начала олимпиады успеть сделать еще N копий. В его распоряжении имеются два ксерокса, один из которых копирует лист за х секунд, а другой – за y. (Разрешается использовать как один ксерокс, так и оба одновременно. Можно копировать не только с оригинала, но и с копии.) Помогите ему выяснить, какое минимальное время для этого потребуется.

Формат входных данных

Во входном файле записаны три натуральных числа N, x и y, разделенные пробелом (1 ≤ N ≤ 2∙10⁸, 1 ≤ x, y ≤ 10).

Формат выходных данных

Выведите одно число – минимальное время в секундах, необходимое для получения N копий.

Примеры

Задача B. Почти палиндром

Слово называется палиндромом, если его первая буква совпадает с последней, вторая – с предпоследней и т.д. Например: "abba", "madam", "x".

Для заданного числа K слово называется  почти палиндромом, если в нем можно изменить не более K любых букв так, чтобы получился палиндром. Например, при K = 2 слова "reactor", "kolobok", "madam" являются почти палиндромами (подчеркнуты буквы, заменой которых можно получить палиндром).

Подсловом данного слова являются все слова, получающиеся путем вычеркивания из данного нескольких (возможно, одной или нуля) первых букв и нескольких последних. Например, подсловами слова "cat" являются слова "c", "a", "t", "ca", "at" и само слово "cat" (а "ct" подсловом слова "cat" не является).

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

Формат входных данных

В первой строке вводятся два натуральных числа: N (1 ≤ N ≤  5 000) – длина слова и K (0 ≤ K ≤  N).

Во второй строке записано слово S, состоящее из N строчных латинских букв.

Формат выходных данных

Требуется вывести одно число – количество подслов слова S, являющихся почти палиндромами (для данного K).

Примеры

Задача C. Рейтинг

Новый учитель математики ввел в школе оригинальную систему оценки учеников – рейтинговую. На каждом уроке школьнику предлагалось выполнить задание, состоящее из нескольких задач. После этого учитель увеличивал рейтинг школьника на число, равное отношению количества решенных им сегодня задач к количеству задач, решенных им на прошлом занятии. Например, если сегодня ученик решил 5 задач, а вчера – две, то к его рейтингу сегодня прибавится  = 2.5. Изначально рейтинг равен нулю; он начинает увеличиваться со второго дня. Если в один из дней какой-то ученик не решал ни одной задачи, то учитель объявлял его полной бездарностью и переводил в другой класс (с облегченным изучением математики), поэтому каждый день все ученики старались решить хотя бы одну задачу.

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

Формат входных данных

В первой строке входного файла записано одно натуральное число N (1 ≤ N ≤ 1 000) – количество уроков, которые провел в школе учитель до того, как его уволили.

В следующей строке записаны числа a₁, a₂, …, a_N  – количество задач, которые учитель предложил школьникам на первом, втором, …, N-м уроках соответственно (1 ≤ a_i ≤ 100).

Формат выходных данных

В первой строке выведите максимальный рейтинг, который может получить школьник за N дней, с точностью не менее 0.001.

Во второй строке выведите N чисел – количество задач, которые должен решить школьник в каждый из дней. Если вариантов несколько, выведите один любой из них.

Примеры

Задача D. Формула–3

В ежегодном чемпионате Флатландии (которая, естественно, является плоским миром) по космическим гонкам "Формула-3" участвуют N космических скутеров, имеющие форму треугольников. До начала гонок скутеры занимают положение в стартовой зоне согласно результатам жеребьевки.

Скутеры стартуют строго по порядку. Каждый скутер, получив команду «старт», уезжает в положительном направлении оси Ox. Следующий скутер стартует лишь тогда, когда предыдущий покинет стартовую зону. Скутеры уезжают строго параллельно оси Ox, скутеры в стартовой зоне не поворачивают и не разворачиваются.

Естественно, что если в момент старта на пути скутера окажется другой скутер, то произойдет авария (даже если скутер заденет лишь угол другого скутера своим углом).

Для уменьшения опасности столкновения скутеров на старте строго соблюдается следующее правило: прямые, параллельные оси Ox и пересекающие какой-то скутер, должны в совокупности пересекать не более 100 других скутеров (прямая, проходящая через одну точку скутера также считается прямой, пересекающей скутер). Например, на приведенном рисунке прямые, параллельные Ox и пересекающие скутер 2, проходят через 2 других скутера (1 и 3), а прямые, проходящие через скутер 1, проходят только через один другой скутер (номер 2).

Главный Судья гонок хочет определить порядок, в котором должны стартовать скутеры, чтобы аварии не произошло. Например, в ситуации, приведенной на рисунке, сначала должен стартовать скутер номер 2 (если попытается стартовать скутер номер 1 или 3, то он столкнется со скутером номер 2). После этого скутеры 1 и 3 могут стартовать в любом порядке (они друг другу не мешают).

Помогите Главному Судье — напишите программу, которая определит какой-нибудь порядок старта скутеров, чтобы аварии не произошло.

Формат входных данных

В первой строке входного файла записано натуральное число N (1 ≤ N ≤ 30 000).

В каждой из следующих N строк записано по 6 чисел: x₁, y₁, x₂, y₂, x₃, y₃ – координаты трех вершин скутера на старте, целые числа, не превосходящие по модулю 10⁶. В начальный момент скутеры не задевают друг друга.

Формат выходных данных

Выведите через пробел N чисел – номера скутеров в том порядке, в котором они могут стартовать. Если решений несколько, выведите одно любое из них. Если решений нет, выведите одно число -1.

Примеры