Задача A. Гирлянда ≡

Условие

У Тимофея есть гирлянда из n лампочек, один из режимов работы которой можно описать следующим образом:

* в течение первой секунды горит первая лампочка;

* в течение второй секунды горит вторая лампочка;

* в течение третьей секунды горят первая и третья лампочки;

* в течение четвертой секунды горят вторая и четвертая лампочки;

* в течение пятой секунды горят первая, третья и пятая лампочки;

* и так далее: в течение m-й секунды горят лампочка с номером m и все лампочки той же четности с номерами, меньше, чем m;

* в течение n + 1 секунды не горит ни одной лампочки.

Описанный цикл из n + 1 секунд повторяется бесконечно.

Определите количество лампочек, которые будут гореть в течение t-й секунды.

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

Первая строка входного файла содержит натуральное число n — количество лампочек в гирлянде. Вторая строка содержит натуральное число t — номер секунды.

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

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

Ограничения

1 ≤ n, t ≤ 10⁹

Система оценки и описание подзадач

Баллы за каждый тест начисляются независимо.

Решения, верно работающие при n = 1, получат не менее 10 баллов.

Решения, верно работающие при n = 2, получат не менее 10 баллов.

Решения, верно работающие при n, t ≤ 100, получат не менее 20 баллов.

Пояснение к примеру

Смотри рисунок. Белый цвет символа — лампочка горит, черный — нет.

Примеры тестов

5
14

1

Задача B. Доска объявлений ≡

Условие

Сегодня на Кафедре изучения квадратов Математического факультета одного известного Дальневосточного ВУЗа появилась новая доска объявлений. Естественно, она имеет квадратную форму со стороной n сантиметров, а её поверхность разбита на n² единичных квадратов для удобного размещения объявлений. Само размещение объявлений регламентируется заведующим кафедрой, который уже издал соответствующий приказ, в котором, в частности, говорится:

1) листочек с объявлением должен иметь квадратную форму, а длина стороны листочка должна выражаться натуральным числом сантиметров;

2) стороны листочка и стороны доски должны быть параллельны, листочек не должен выходить за пределы доски;

3) левый верхний угол листочка должен совпадать с одним из узлов квадратной сетки доски;

4) листочки с объявлениями не могут перекрывать друг друга, но могут касаться сторонами или вершинами;

5) размещать листочки можно в любом свободном месте доски, если это не противоречит всем предыдущим пунктам приказа;

6) запрещается сдвигать или снимать чужие объявления.

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

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

Первая строка входного файла содержит два натуральных числа, записанных через пробел: n и m.

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

Выведите одно неотрицательное целое число - длину стороны второго объявления.

Ограничения

1 ≤ m ≤ n ≤ 10⁹

Система оценки и описание подзадач

Баллы за каждый тест начисляются независимо.

Пояснение к примеру

В примере дана доска размером 3 и объявление размером 2. Разместить объявление со стороной, превышающей 1, невозможно.

Примеры тестов

3 2

1

Задача C. Небоскреб ≡

Условие

Артем и Женя обожают строить здания из кубиков. Они уже строили из них гаражи, домики и даже средневековые замки... Сегодня ребята решили возвести небоскреб. У Артема есть n синих кубиков, а у Евгения m красных. По мысли ребят, построенный небоскреб должен представлять собой два прямоугольных параллелепипеда с квадратными основаниями разного размера, установленные один на другой. Мальчики хотят, чтобы каждый из них построил свою часть многоэтажного строения исключительно из всех своих кубиков, а потом установить один параллелепипед на другой.

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

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

Первая строка входного файла содержит три натуральных числа, записанных через пробел: n, m и k.

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

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

Ограничения

1 ≤ n, m, k ≤ 10⁹

Система оценки и описание подзадач

Баллы за каждый тест начисляются независимо.

Пояснение к примерам

В первом примере у Артема 729 кубиков, а у Жени 1024. Наибольшая высота небоскреба, который может быть построен дома, не может превышать 15. Ребята действуют так: сначала Евгений строит из своих кубиков основание небоскреба в виде прямоугольного параллелепипеда: 16 × 16 × 4 (обратите внимание — основание параллелепипеда обязательно должно быть квадратным). Потом Артем устанавливает сверху на постройку Жени свой прямоугольный параллелепипед: 9 × 9 × 9, и высота небоскреба становится равна 13. Большей высоты с учетом всех ограничений достичь нельзя.

Во втором примере у ребят не получится составить небоскреб. Артем может построить свою часть в виде единственно возможного прямоугольного параллелепипеда: 1 × 1 × 17, Женя (аналогично): 1 × 1 × 19. Но, во-первых, обе построенные ими части будут иметь равное основание, а во вторых, общая высота небоскреба 36 превышает высоту помещения.

Примеры тестов

729 1024 15

13

17 19 30

0

Задача D. Прыжки ≡

Условие

Одна из дворовых игр детства автора задачи называлась "Прыжки". Рисовался мелом прямоугольник, разбивался на квадраты с числами внутри от 1 до k (по числу квадратов) и потом детвора пыталась по очереди пропрыгать по всем квадратам в порядке возрастания их номеров таким образом, чтобы ни разу не приземлиться на линии сетки.

Назовем расстоянием прыжка между квадратами с числами x и x + 1 расстояние между центрами этих квадратов (считая сторону квадрата равной 1). Так, расстояние прыжка между квадратами с числами 1 и 2 на приведенном на рисунке поле равно √2, между квадратами с числами 2 и 3 равно 1, между квадратами с числами 3 и 4 равно √10 (вычисляется по теореме Пифагора).

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

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

Первая строка входного файла содержит два натуральных числа, записанных через пробел: n и m. В следующих n строках через пробел расположено по m натуральных чисел x_i — номера квадратов игрового поля. Гарантируется, что все x_i составляют некоторую перестановку чисел от 1 до n × m.

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

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

Ограничения

1 ≤ n, m ≤ 10⁵

2 ≤ n × m ≤ 10⁵

Система оценки и описание подзадач

Баллы за каждый тест начисляются независимо.

Пояснение к примеру

Наибольшее расстояние прыжка для данного в примере поля требуется для того, чтобы добраться с квадрата номер 3 до квадрата номер 4 (оно равно √10. Требуется вывести натуральное число — квадрат этого расстояния.

Примеры тестов

4 3
8 4 11
5 7 12
1 10 9
6 2 3

10

Задача E. Сравнительная степень ≡

Условие

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

long — longer

clean — cleaner

full — fuller

Если прилагательное заканчивается на согласную + -y, то -y заменяется на -i:

funny — funnier

Если прилагательное заканчивается на согласную + -e, то -e отбрасывается:

large — larger

Если прилагательное заканчивается на согласную + гласную + согласную, последняя согласная удваивается:

thin — thinner

big — bigger

По предложенному прилагательному образуйте его сравнительную степень. Считайте, что в английском языке шесть гласных букв: a, e, i, o, u, w.

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

Единственная строка входного файла содержит строку s — английское прилагательное, составленное из строчных букв.

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

Выведите одну строку — это же прилагательное в сравнительной степени.

Ограничения

3 ≤ len(s) ≤ 10

Система оценки и описание подзадач

Баллы за каждый тест начисляются независимо.

Примеры тестов

cool

cooler