Задача A. Наибольшее число цепочек ≡

Условие

Пусть имеется множество всех возможных цепочек, состоящих из конечного числа звеньев. Из указанных цепочек необходимо построить последовательность такую, чтобы каждая следующая цепочка в ней была ровно на d звеньев больше предыдущей, а суммарная длина всех входящих в нее цепочек равнялась n. Максимально возможное количество цепочек, из которых может состоять такая последовательность, обозначим за A(n, d).

Требуется вычислить значения A(n, d) для всех натуральных n, не превосходящих заданного m, при некотором фиксированном d.

Формат входного файла

Входной файл "input.txt" содержит два натуральных числа: d и m.

Формат выходного файла

Выходной файл "output.txt" должен содержать последовательность значений A(n, d), расположенных в порядке возрастания величины n = 1, 2, …, m.

Ограничения

d ≤ m ≤ 10⁵

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

1 10

1 1 2 1 2 3 2 1 3 4

2 10

1 1 1 2 1 2 1 2 3 2

Задача B. Составные блоки ≡

Условие

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

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

Совпадающие между собой ребра (в которых две и более ячейки соприкасаются друг с другом) полагаются тождественными и рассматриваются как одно общее ребро. Так, например, блок размером 2 × 2 × 2 состоит из 8-ми ячеек и содержит в себе 54 ребра.

Требуется определить, существует ли прямоугольный блок, состоящий из m кубических ячеек и при этом имеющий ровно n ребер.

Формат входного файла

Во входном файле "input.txt" содержатся два натуральных числа: m и n.

Формат выходного файла

Выходной файл "output.txt" должен содержать одно из следующих значений:

1 — если заданный блок существует;

0 — в противном случае.

Ограничения

0 < m < 2³², 0 < n < 2⁶⁴

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

8 54

1

6 43

0

Задача C. Нули в окончании числа ≡

Условие

Обозначим за P(A, B) результат произведения всех натуральных чисел от A до B включительно.

Для заданных значений A, B и q требуется определить количество нулевых разрядов, которыми оканчивается q-ичная запись числа P(A, B).

Формат входного файла

Входной файл "input.txt" содержит три натуральных числа: A, B и q.

Формат выходного файла

Выходной файл "output.txt" должен содержать одно единственное число, указывающее количество нулевых разрядов.

Ограничения

0 < A ≤ B < 2⁶⁴, 2 ≤ q < 2³²

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

1 100 10

24

9 75 120

17

Задача D. Два кольца на плоскости ≡

Условие

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

Пусть имеются два кольца, каждое из которых задается координатами своего центра (x_i, y_i), а также внутренним q_i и внешним r_i радиусами.

Требуется определить площадь их пересечения.

Формат входного файла

Во входном файле "input.txt" содержится набор вещественных значений, определяющих положение исходных колец: x₁, y₁, q₁, r₁, x₂, y₂, q₂, r₂.

Формат выходного файла

Выходной файл "output.txt" должен содержать площадь их пересечения, указанную с точностью до 5-го знака после запятой.

Ограничения

0 ≤ q₁ ≤ r₁, 0 ≤ q₂ ≤ r₂

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

-2.16000 -2.45000  1.27000  2.35000
 1.00000  0.19000  3.00000  4.00000

2.24485

-3.64000 -2.75000  1.00000  2.95000
 5.00000 -3.19000  2.00000  4.00000

0.00000

Задача E. Три подвижные частицы ≡

Условие

Пусть имеются три частицы, положение которых в момент времени t = 0 задается двумерными координатами: (x₁, y₁), (x₂, y₂) и (x₃, y₃).

Полагается, что в течение всего последующего времени каждая i-я частица, независимо от остальных,
совершает прямолинейное движение с некоторой постоянной скоростью (u_i, v_i).

Требуется определить наиболее ранний момент времени T ≥ 0, когда они окажутся на одной прямой.

Формат входного файла

Входной файл "input.txt" содержит последовательность целых чисел:
x₁, y₁, u₁, v₁, x₂, y₂, u₂, v₂, x₃, y₃, u₃, v₃.

Формат выходного файла

Выходной файл "output.txt" должен содержать значение T, указанное с точностью до 5-го знака после запятой.

В случае если подходящее решение не может быть найдено, в выходной файл необходимо вывести  − 1.

Ограничения

Все входные значения являются целыми десятичными числами.

 − 10⁴ ≤ (x_i, y_i, u_i, v_i) ≤ 10⁴.

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

 2500  2500 -3000 -3000
-1000     0  1000  4000
    0 -1000  4000  3000

 0.48990

-1097   236  1000  1000
  200   178  1500   500
    0  -500 -1240   356

-1

Задача F. Приведение многочлена ≡

Условие

Пусть имеется многочлен, представленный в следующем виде: C₀ ⋅ (x − C₁) ⋅ …  ⋅ (x − C_n), где все C_i принадлежат кольцу вычетов по некоторому заданному модулю p.

Требуется привести его к каноническому виду: A₀ + A₁ ⋅ x + …  + A_n ⋅ xⁿ.

Формат входного файла

В начале входного файла "input.txt" содержится значение модуля p и натуральное число n. Далее следует набор значений C_i, где i = 0, 1, …, n.

Формат выходного файла

Выходной файл "output.txt" должен содержать массив коэффициентов A_i.

Ограничения

2 ≤ p < 2⁶⁴, 0 ≤ C_i < p, 0 ≤ n ≤ 500

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

100 5
2
13
4
37
6
29

48
68
90
90
22
2

2 4
1
0
1
0
1

0
0
1
0
1

Задача G. Представление дробей ≡

Условие

Пусть имеется некоторая простая дробь, заданная своим числителем A и знаменателем B.
Требуется преобразовать указанную дробь, представив ее в одном из следующих форматов:

• правильная дробь: <числитель> / <знаменатель> ;
• смешанная дробь: <целая_часть> ( <числитель> / <знаменатель> ) ;
• десятичная дробь: <целая_часть>.<дробная_часть> ;
• целое число: <целая_часть> .

Если дробная часть равна нулю, результат записывается как целое число.
В противном случае полученную дробь следует привести к несократимому виду
так, чтобы <числитель> был меньше, чем <знаменатель>.

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

Формат входного файла

Во входном файле "input.txt" содержатся два натуральных числа: A и B.

Формат выходного файла

Выходной файл "output.txt" должен содержать дробь A / B,
отформатированную в соответствии с условием задачи.

Ограничения

0 < (A, B) < 2⁶⁴

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

1736744720710
5067073484375

11977549798 / 34945334375

57295346800
351486000

163 ( 7822 / 878715 )

10298463668
40000000

257.4615917

1675223508
13509867

124

Задача H. Возведение большого числа в степень ≡

Условие

Пусть имеется неотрицательное целое число A, представленное в виде массива своих цифр.
Требуется возвести его в некоторую заданную степень n.

Формат входного файла

Первая строка входного файла "input.txt" представляет собой десятичную запись числа A.
Следующая строка содержит показатель степени n.

Формат выходного файла

Выходной файл "output.txt" должен содержать результат возведения в степень,
представленный в десятичной системе счисления.

Ограничения

0 ≤ A ≤ 10⁵⁰, 0 < n ≤ 1000

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

10203756485819806252197658031528043601970
2

104116646421909761950282879573175588809976767764774752111453905887721451787880900

55786
17

490827381405222212342433355512086149590506305271663102056527621790991920279453696

Задача I. НОД больших чисел ≡

Условие

Юный математик Вася очень любит числа. А еще больше он любит раскладывать их на делители. Однажды ему приснилось достаточно большое q-ичное число, из которого он запомнил только последние n цифр.

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

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

Формат входного файла

В начале входного файла "input.txt" хранятся два натуральных числа q и n, после чего следует ровно n q-ичных разрядов, для которых требуется решить поставленную задачу.
При этом для обозначения цифр, лежащих в диапазоне от 10 до 35, используются строчные символы латинского алфавита.

Формат выходного файла

Выходной файл "output.txt" должен содержать искомый делитель, также записанный в q-ичной системе счисления.

Ограничения

2 ≤ q ≤ 36, 0 < n ≤ 4000

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

36 41
10360k898faq2lvf8j4rxhifkd9ilnnobm9il766r

6kzw4bjxrz9chm64eqktymn29

2 25
1000000000000000000000000

1000000000000000000000000

Задача J. Сжатие бинарной строки ≡

Условие

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

Пусть имеется некоторая бинарная последовательность (состоящая из нулей и единиц), разбитая на блоки фиксированной длины. При этом заранее известно, что каждый такой блок содержит в себе ровно n нулей и m единиц.

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

Несложно показать, что размер полученного алфавита обратно пропорционален значению |n − m|. Так, в предельном случае, когда n (или m) равно нулю, алфавит будет состоять всего-лишь из одного символа. В свою очередь, чем меньше размер алфавита, тем меньшее число бит будет требоваться для представления номеров содержащихся в нем символов.

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

Формат входного файла

В первой строке входного файла "input.txt" записаны два целых неотрицательных числа n и m. Далее следует текстовая строка, состоящая из n нулей и m единиц.

Формат выходного файла

Выходной файл "output.txt" должен содержать результирующий код указанной строки, представленный в двоичной системе счисления (ведущие нули при этом можно опустить).

Ограничения

0 < (n + m) ≤ 2 ⋅ 10⁴

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

8 24
00000001101111111111111111111111

000000000000000000000010

24 8
01000100000011001000001101000000

011000111110100111000100

Задача K. Очередь в поликлинике ≡

Условие

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

За отдельно взятые сутки была собрана статистика, состоящая из моментов времени t_i, указанных в талоне каждого i-го пациента, и времени m_i, которое было затрачено на его прием.
Требуется определить максимальную длину очереди, которая имела место за текущие сутки, а также время окончания приема последнего пациента.

При решении задачи следует полагать, что все t_i и m_i указывают время в минутах и могут принимать только целочисленные значения. Число минут в сутках полагается равным t_max.

Также известно, что пациентам, которые не успели пройти прием в течение суток, очередь автоматически продлевается на следующий день.
В качестве окончания приема для всех таких пациентов указывается максимально допустимое время t = t_max.

Формат входного файла

В начале входного файла "input.txt" содержится пара натуральных чисел t_max и n, за которыми следует ровно n записей, представленных в виде пар положительных целых чисел t_i и m_i. При этом полагается, что все они упорядочены по возрастанию t_i.

Формат выходного файла

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

Ограничения

0 < t_max ≤ 10⁶, 0 < (t_i, m_i) ≤ t_max, t_i < t_i + 1

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

1440 10
1 1
2 1
3 2
54 2
349 1
720 2
1024 2
1175 2
1193 1
1205 3

0 1208

1440 10
1 1
2 4
6 134
79 12
136 5
214 173
345 15
1075 2
1093 114
1205 3

2 1210

Задача L. Пузыри на плоскости ≡

Условие

Рассмотрим множество непрерывно растущих пузырей, расположенных на плоскости. Каждый такой пузырь представляет собой круг, заданный координатами своего центра (x_i, y_i) и радиальной скоростью v_i, указывающей приращение его радиуса за единицу времени.

Известно, что рост отдельно взятого пузыря будет остановлен, как только он достигнет границы любого другого. При этом полагается, что в начальный момент времени (t = 0) радиусы всех пузырей равны нулю.

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

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

Формат входного файла

Во входном файле "input.txt" хранится натуральное число n, указывающее количество пузырей.
Далее следует набор из 3 × n вещественных чисел: x_i, y_i, v_i.

Формат выходного файла

Выходной файл "output.txt" должен содержать время окончания роста всех таких пузырей
и значения их радиусов r_i в конечный момент времени.
Все значения должны быть записаны с точностью до 5-го знака после запятой.

Ограничения

 − 100 ≤ (x_i, y_i) ≤ 100, 0 ≤ v_i ≤ 20,

2 ≤ n ≤ 500

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

 5
 3.05780 -1.53000  2.92010
-9.05000 -2.37000  1.57000
-7.01400  1.09000  3.06000
 4.05600  8.41000  2.24000
-3.89000 -3.57000  1.00000

2.05182
5.39393
1.36132
2.65327
4.59607
1.84717

 5
-1.15000  0.96070  3.01280
 9.38000 -2.37000  1.57000
-1.15000  0.96070  3.06000
 6.43010  4.23080  0.00000
 3.89000 -3.57000  2.00000

1.57412
0.00000
2.47137
0.00000
0.00000
3.14825

Задача M. Ловушка для подвижных частиц ≡

Условие

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

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

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

Определим кольцо, как область, заключенную между двумя окружностями с общим центром (x₀, y₀) и разными радиусами: r₂ > r₁ > 0. В этом случае исходное множество частиц можно условно разбить на три группы:

1. частицы, попадающие во внутренний круг с центром в точке (x₀, y₀) и радиусом r₁ > 0;
2. частицы, заключенные между двумя окружностями с радиусами r₁ и r₂;
3. частицы, лежащие за пределами внешнего круга с радиусом r₂ > r₁.

Рассмотрим поведение указанных частиц на временном интервале от 0 до T.

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

Требуется написать программу, которая по известному начальному положению частиц, исходным компонентам скорости и параметрам кольцевой области, производит расчет их траекторий в течение заданного промежутка времени. В качестве ответа вывести координаты положения частиц в равноотстоящие моменты времени t_k = k ⋅ (T / m), где k = 1, 2, …, m.

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

Формат входного файла

В первой строке входного файла "input.txt" содержатся параметры расчетной области: x₀, y₀, r₁, r₂. Во второй строке указано значение T, задающее длину временного интервала, и число его подынтервалов m. Далее следует натуральное число n и последовательность из 4 × n вещественных чисел, задающих начальные координаты и скорости каждой из частиц: x_i, y_i, u_i, v_i, где i = 1, 2, …, n.

Формат выходного файла

Выходной файл "output.txt" должен содержать координаты положения частиц в моменты времени t_k (k = 1, 2, …, m), расположенные в том же порядке, что и во входном файле. Все значения должны быть указаны с точностью до 5-го знака после запятой.

Ограничения

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

2 ≤ r₁ ≤ (r₂ − 2) ≤ 10, 0 < T ≤ 20, 0 < m ≤ 10,

u_i² + v_i² ≤ 25, 0 < n ≤ 4000

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

 1.62400  4.86000  2.01152  4.21450
10.00000  4
 5
 2.24501 -2.75130 -0.46250  1.00000
-1.39080  6.92500  0.02731 -1.75240
-7.10643  2.32470  0.10561  0.27435
 2.07640  4.96800 -0.04658  0.94071
 3.00000  3.75400 -1.04060 -1.04520

 1.08876 -0.25130
-1.32252  2.54400
-6.84240  3.01057
 1.79231  6.39753
 0.09054  3.90417

-0.67633 -0.22719
 2.36153  1.88787
-6.57838  3.69645
 0.85566  4.23718
 1.22695  6.69642

-2.86015 -1.90584
 4.61717  4.01900
-6.31435  4.38232
 1.39629  4.06765
 3.58175  4.57937

-5.04397 -3.58449
 4.04359  7.86965
-6.05033  5.06820
 3.19249  5.59017
 0.69049  3.16606

Задача N. Число кодонов в ДНК ≡

Условие

Цепочка молекулы ДНК представляет собой последовательность из четырех разновидностей нуклеотидов,
для обозначения которых используются буквы латинского алфавита: A, C, G, T.

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

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

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

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

1. первый кодон был записан полностью;
2. от первого кодона осталось только два последних символа;
3. от первого кодона остался только один символ.

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

Формат входного файла

Входной файл "input.txt" содержит заданную последовательность нуклеотидов.

Формат выходного файла

Выходной файл "output.txt" должен содержать все найденные кодоны,
расположенные в лексикографическом порядке.

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

Ограничения

Длина исходной последовательности
не превосходит 10⁷.

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

AGTAGTCATAGAGTCT

AGA 1 0 0
AGT 2 1 0
ATA 0 0 1
CAT 1 0 0
GAG 0 0 1
GTA 0 0 1
GTC 1 0 1
TAG 0 2 0
TCA 0 1 0
TCT 0 0 1

TA

Задача O. Форматированные строки ≡

Условие

Пусть имеются две строки, содержащие набор слов, состоящих из цифр и символов латинского алфавита, и отделенных друг от друга пробелами либо знаками препинания ('-', '.', ',', ':', ';', '!', '?'). Регистр символов, а также количество подряд идущих пробелов роли не играет (любое число пробелов воспринимается как один символ). Пробелы, расположенные по краям строки либо отделяющие знаки препинания, игнорируются.

Для определения формата текста в пределах каждой такой строки используются теги следующих видов:

<b>текст</b> — жирный шрифт;

<i>текст</i> — курсив.

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

Теги могут разбивать слово на части: <i><b>тек</b>ст</i>. В этом случае, отдельные части слова будут иметь различное форматирование.

В свою очередь, на пробельные символы форматирование не распространяется.

Требуется сравнить две такие строки.

Формат входного файла

Во входном файле "input.txt" содержатся две строки, между которыми необходимо выполнить сравнение.

Формат выходного файла

Выходной файл "output.txt" должен содержать одно из следующих значений:

2 — текст в обеих строках совпадает и имеет одинаковый формат;

1 — текст в обеих строках совпадает, но имеет разный формат;

0 — обе строки содержат разный текст.

Ограничения

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

Длина каждой строки не превосходит 3 ⋅ 10⁶.

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

<i>THIS </i><i>IS   <b>SPARTA!!!</b></i>
<i>this   is    <b>Sparta  ! !!</b></i>

2

<i>THIS IS   <b>SPARTA!!!</b></i>
<i>this is</i> <b>Sparta!!!</b>

1

<i>THIS IS   <b>SPARTA!!!</b></i>
<i>This Is   <b>Sparta!</b></i>

0

Задача P. Константные выражения ≡

Условие

Пусть имеется программа, записанная на императивном языке программирования, поддерживающем команды следующего вида:

<переменная> = <выражение> — присвоить переменной результат заданного выражения.

Выражение может состоять из арифметических операций ('+', '-', '*', '/'), круглых скобок, переменных и целочисленных констант. Между ними также допускается произвольное число пробелов. При этом знак минуса используется здесь для обозначения как бинарной, так и унарной операции. Операции ('+', '-') имеют меньший приоритет, чем ('*', '/'). Операции, обладающие одинаковым приоритетом, выполняются слева направо.

В качестве имен переменных выступают символы латинского алфавита (регистр их написания неважен). Полагается, что все они принадлежат к знаковому 32-разрядному целому типу и могут принимать значения из диапазона от  − 2³¹ до 2³¹ − 1. Константы представляют собой числа, записанные в десятичной системе счисления и лежащие в диапазоне от 0 до 2³¹ − 1.

Изначально всем переменным присваиваются нулевые значения. Арифметическое переполнение и деление на ноль приводят к неопределенному результату, для обозначения которого используется символ '#' (ASCII 35). Все операции с неопределенным значением (кроме умножения на ноль) также возвращают '#'.

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

Формат входного файла

Во входном файле "input.txt" построчно содержатся команды указанного языка.

Формат выходного файла

В выходной файл "output.txt" следует вывести пары: <переменная> <значение>. При этом переменные, которые отсутствуют в левых частях выражений, могут быть проигнорированы.

Ограничения

Полагается, что все представленные команды включают в себя не более 50 арифметических операций и не содержат синтаксических ошибок.

Число открывающихся скобок также ограничено и не превосходит 30.

Входная программа состоит как минимум из одной команды. Общее число команд не превосходит 1000.

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

i = 1045
B = (a + i) * 23 - 190
c = B
i = - 4 + i / 10
c = i - 138

b 23845
c -38
i 100

i = B + 14903 * A
B = 100 / (i * 2)
C = b /(c +a * E)
i = i - u * C
B = i + 350

b 350
c #
i 0

Задача Q. Число вхождений подстроки ≡

Условие

Пусть имеется текстовая строка S, состоящая из произвольных печатных символов (ASCII 32-126). Требуется определить общее число ее подстрок, совпадающих с некоторым заданным образцом T.

Для решения задачи следует воспользоваться алгоритмом Кнута-Морриса-Пратта.

Формат входного файла

В заголовке входного файла "input.txt" содержится строка T, выступающая в роли образца. Далее следует строка S, в которой необходимо выполнить поиск.

Формат выходного файла

Выходной файл "output.txt" должен содержать число найденных подстрок.

Ограничения

0 < |T| ≤ 5 ⋅ 10⁴, 0 ≤ |S| ≤ 2 ⋅ 10⁷

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

ABCDEF
123 AB ABCDEFABCDEF ABCDEF45ABCDEFuZ

4

ABCABC
ZEt AB ABCABCABCABC ABC45-ABCABCABC+

5

Задача R. Перемешанные символы ≡

Условие

Пусть имеется текстовая строка, состоящая из произвольных печатных символов (ASCII 33-126).

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

Формат входного файла

Входной файл "input.txt" содержит исходную строку.

Формат выходного файла

Выходной файл "output.txt" должен содержать строку, приведенную к требуемому виду.

В случае, если это невозможно, выходной файл следует оставить пустым.

Ограничения

Полагается, что длина исходной строки
лежит в диапазоне от 1 до 2 ⋅ 10⁷.

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

AAAAAbbbbbaaaaaAAAaaaacccAAcccbb

aAabcAabcAabcAabcAabcAabAaAaAbAc

32213312222222032022992211222222

Задача S. Разноцветные кубики ≡

Условие

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

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

Формат входного файла

В заголовке входного файла "input.txt" хранится число доступных разновидностей наклеек n. Далее следует набор из n значений A_i, указывающих число наклеек каждого вида.

Формат выходного файла

Выходной файл "output.txt" должен содержать максимально возможное число кубиков.

Ограничения

0 < n ≤ 10⁶, 0 < A_i ≤ 10⁹

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

8

23
31
742
4
5
84
6
19

6

5

12
145
7
94
2

0

Задача T. Сортировка записей ≡

Условие

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

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

При сравнении отдельных полей необходимо придерживаться следующих правил: вещественные значения должны быть упорядочены по возрастанию; знаковые целые — по убыванию; беззнаковые — по возрастанию; символьные значения — по убыванию своих позиций в таблице ASCII; упорядочение строк производится по возрастанию (в лексикографическом порядке).

Формат входного файла

В первой строке входного файла "input.txt" содержится пара натуральных чисел n и m, указывающих общее количество таких записей и число их полей. Во второй строке содержится массив из m символьных значений (разделенных пробелами), указывающих тип каждого поля в соответствии со следующей таблицей:

• 'd' — вещественное число, записанное с точностью до 5-го знака после запятой;
• 'i' — целое знаковое число, лежащее в диапазоне от -2⁶³ до 2⁶³-1;
• 'u' — целое беззнаковое число, лежащее в диапазоне от 0 до 2⁶⁴-1;
• 'c' — символьное значение (ASCII 32-126);
• 's' — строка (содержит от 0 до 24 символов).

Далее следует массив из m целых чисел p_i, устанавливающих приоритеты указанных полей. Начиная с четвертой строки располагается массив записей. При этом значение каждого поля занимает ровно одну строку.

Формат выходного файла

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

Ограничения

n ≤ 2 ⋅ 10⁴, m ≤ 10, 0 ≤ p_i < 10

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

5 4
i s d c
2 9 7 0
-1
QWERTY
3.90000
a
-9
ASUS
0.47000
t
75
QWERTY
0.10000
x
9
ASKOLD
8.05000
b
0
ASUS
-0.00075
y

3
4
1
2
0

5 4
i u d c
9 8 1 3
-1
48
-3.50000
a
-9
15
0.90000
w
-9
10
4.70000
b
-1
48
-0.70000
z
-1
48
1.56000
p

3
4
0
2
1