Задача A. Кодирование набора чисел ≡

Условие

Пусть имеется последовательность целых десятичных чисел строго больших нуля:

4 3 6 7 10 26 100 40 21 14 12 22 148 29 18 81 28 31 27 20.

Требуется закодировать данную последовательность следующим образом:

1. Вначале каждое такое число необходимо перевести в двоичную систему счисления, задействовав минимально возможное число бит, в которое оно может уместиться.
2. Далее требуется выполнить конкатенацию (слияние, склеивание) всех полученных кодов в порядке исходной последовательности.
3. Полученное двоичное число следует представить в 16-ричной системе счисления, задействовав цифры от 0 до 9 и строчные буквы латинского алфавита от a до f.

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

Полученный ответ введите в текстовое поле:

Задача B. Поиск кратчайшего пути ≡

Условие

Пусть имеется граф из 26 вершин, промаркированных заглавными буквами латинского алфавита от A до Z (см. рисунок).

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

Требуется определить кратчайший маршрут, ведущий из вершины A в вершину Z
и проходящий через как можно большее число вершин.

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

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

Полученный ответ введите в текстовое поле:

Задача C. Космический побег ≡

Условие

Инопланетянин по имени "Скр" живет в плоском мире. Скр снова не доел мамин суп, поэтому теперь он в бегах... Летя на своём корабле он увидел перед собой маленькую планету - круг радиуса r. На планете нет ничего, кроме ярких фонарей. Эти фонари настолько яркие, что освещают на сколько угодно большое расстояние, однако сквозь поверхность планеты они просветить не могут. Всего n фонарей, i-ый фонарь представляет из себя тонкий столб высоты h_i, на верхушке которого располагается светящийся элемент, освещающий все в зоне своей видимости. Укажем точку отчета - произвольную точку на поверхности планеты. И для каждого фонаря известно вещественное число a_i - угол в радианах по часовой стрелки от точки отсчета до основания фонаря (см иллюстрацию).

Скр пытается уйти от погони, поэтому хочет спрятаться в тени, то есть в такой точки планеты, которую не освещает ни один фонарь.

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

Фонари располагаются перпендикулярно поверхности планеты.

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

В первой строке входных данных располагается целое число n - количество фонарей на планете.

Во второй строке одно вещественное число r - радиус планеты.

В следующих n строках располагаются по два вещественных числа - a_i и h_i - угол в радианах от начальной точки до основания фонаря и высота фонаря.

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

Выведите в единственной строке YES, если существует место, в котором Скр может спрятаться, и NO в ином случае.

Ограничения

1 ≤ n ≤ 10⁵

1 ≤ r ≤ 100

1 ≤ a_i ≤ 2 * π

0 < h_i < 100

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

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

Иллюстрации к примерам

Иллюстрация к примеру 1



Иллюстрация к примеру 2



Иллюстрация к примеру 3

В иллюстрациях начало отсчёта располагается в верхней точке.

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

3
4
1.047197551 1.000000000
3.141592653 2.000000000
5.235987755 0.500000000

YES

3
4
1.047197551 11.000000000
3.141592653 4.000000000
5.235987755 6.000000000

NO

3
4
1.047197551 11.000000000
3.141592653 4.000000000
4.712388980 5.000000000

YES

Задача D. Саша и кофе ≡

Условие

Программист Саша пьет кофе всегда из одной и той же кружки, которую он никогда не моет.

Когда кофе находится в кружке достаточно долго, оно оставляет на ней кофейное кольцо.

Иногда Саша подливает кофе в кружку, от чего уровень кофе поднимается, и все кольца, которые оказываются ниже уровня кофе растворяются.

Саша может выполнить 3 действия:

1. Налить в кружку coffee_i миллилитров кофе.
2. Выпить coffee_i миллилитров кофе.
3. Определить сколько кофейных колец сейчас на кружке.

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

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

Первая строка входных данных содержит число n - количество действий, которые сделал Саша.

В следующих n строках идет:

• + coffee_i - Саша доливает в кружку coffee_i миллилитров кофе.
• - coffee_i - Саша выливает из кружки coffee_i миллилитров кофе.

Гарантируется, что Саша не пытается выпить больше кофе, чем есть в кружке. Изначально в кружке нет ни миллилитра кофе.

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

Требуется вывести количество кофейных колец, которое было на кружке после каждого действия Саши. Каждое в новой строке.

Ограничения

0 < n ≤ 10⁷

0 < с_i ≤ 10⁸

Гарантируется, что объем кофе в стакане никогда не достигнет 2³².

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

14
+ 108
+ 105
+ 110
+ 101
- 32
+ 32
+ 32
+ 32
+ 32
- 103
- 114
- 101
- 101
- 100

1
1
1
1
2
1
1
1
1
2
3
4
5
6

9
+ 1
- 1
+ 1
+ 1
+ 2
+ 3
- 4
+ 1
+ 7

1
1
1
1
1
1
2
2
1

Задача E. Стильная гирлянда ≡

Условие

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

Однако полученная гирлянда не соответствует стилю 2024 года, из-за чего дед мороз поручил своим эльфам вырвать из гирлянды наименьшее количество лампочек так, чтобы полученная гирлянда соответствовала стилю 2024 года.

Изначальная гирлянда задается строкой s. Гирлянда является стильной, если она состоит из последовательно соединенных строк k.

Более формально если строка k = k₁, k₂, …, k_n, то стильная гирлянда будет представлять из себя последовательность следующего вида:

k₁₁, k₂₁…k_n1, k₁₂…k_n2, …k_nm. Где k_ij =  = k_i.

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

Первая строка входных данных - s.

Вторая строка - k.

Гарантируется, что обе строки состоят только из латинских букв. (строчных и прописных)

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

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

Ограничения

0 < length(s) ≤ 10⁷

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

acbacabba
abac

4

abac
acbacabba

0