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

Автор:А. Баранов   Ограничение времени:1 сек
Входной файл:input.txt   Ограничение памяти:2 Мб
Выходной файл:output.txt  

Условие

Пусть имеется множество всех возможных цепочек, состоящих из конечного числа звеньев. Из указанных цепочек необходимо построить последовательность такую, чтобы каждая следующая цепочка в ней была ровно на 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 ≤ 105

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

Входной файл (input.txt) Выходной файл (output.txt)
1
1 10
1 1 2 1 2 3 2 1 3 4
2
2 10
1 1 1 2 1 2 1 2 3 2

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

Автор:А. Баранов   Ограничение времени:1 сек
Входной файл:input.txt   Ограничение памяти:2 Мб
Выходной файл:output.txt  

Условие

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

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

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

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

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

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

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

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

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

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

Ограничения

0 < m < 232, 0 < n < 264

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

Входной файл (input.txt) Выходной файл (output.txt)
1
8 54
1
2
6 43
0

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

Автор:А. Баранов   Ограничение времени:1 сек
Входной файл:input.txt   Ограничение памяти:2 Мб
Выходной файл:output.txt  

Условие

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

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

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

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

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

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

Ограничения

0 < A ≤ B < 264, 2 ≤ q < 232

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

Входной файл (input.txt) Выходной файл (output.txt)
1
1 100 10
24
2
9 75 120
17

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

Автор:А. Баранов   Ограничение времени:1 сек
Входной файл:input.txt   Ограничение памяти:2 Мб
Выходной файл:output.txt  

Условие

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

Пусть имеются два кольца, каждое из которых задается координатами своего центра (xi, yi), а также внутренним qi и внешним ri радиусами.

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

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

Во входном файле "input.txt" содержится набор вещественных значений, определяющих положение исходных колец: x1, y1, q1, r1, x2, y2, q2, r2.

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

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

Ограничения

0 ≤ q1 ≤ r1, 0 ≤ q2 ≤ r2

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

Входной файл (input.txt) Выходной файл (output.txt)
1
-2.16000 -2.45000  1.27000  2.35000
 1.00000  0.19000  3.00000  4.00000
2.24485
2
-3.64000 -2.75000  1.00000  2.95000
 5.00000 -3.19000  2.00000  4.00000
0.00000

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

Автор:А. Баранов   Ограничение времени:1 сек
Входной файл:input.txt   Ограничение памяти:2 Мб
Выходной файл:output.txt  

Условие

Пусть имеются три частицы, положение которых в момент времени t = 0 задается двумерными координатами: (x1, y1), (x2, y2) и (x3, y3).

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

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

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

Входной файл "input.txt" содержит последовательность целых чисел:
x1, y1, u1, v1, x2, y2, u2, v2, x3, y3, u3, v3.

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

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

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

Ограничения

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

 − 104 ≤ (xi, yi, ui, vi) ≤ 104.

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

Входной файл (input.txt) Выходной файл (output.txt)
1
 2500  2500 -3000 -3000
-1000     0  1000  4000
    0 -1000  4000  3000
 0.48990
2
-1097   236  1000  1000
  200   178  1500   500
    0  -500 -1240   356
-1

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

Автор:А. Баранов   Ограничение времени:1 сек
Входной файл:input.txt   Ограничение памяти:8 Мб
Выходной файл:output.txt  

Условие

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

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

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

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

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

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

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

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

Ограничения

0 < tmax ≤ 106, 0 < (ti, mi) ≤ tmax, ti < ti + 1

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

Входной файл (input.txt) Выходной файл (output.txt)
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
2
1440 10
1 1
2 4
6 134
79 12
136 5
214 173
345 15
1075 2
1093 114
1205 3
2 1210

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

Автор:А. Баранов   Ограничение времени:1 сек
Входной файл:input.txt   Ограничение памяти:4 Мб
Выходной файл:output.txt  

Условие

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

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

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

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

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

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

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

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

Ограничения

 − 100 ≤ (xi, yi) ≤ 100, 0 ≤ vi ≤ 20,

2 ≤ n ≤ 500

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

Входной файл (input.txt) Выходной файл (output.txt)
1
 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
2
 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

Задача H. Точки на n-мерном параллелепипеде

Автор:А. Баранов   Ограничение времени:1 сек
Входной файл:input.txt   Ограничение памяти:4 Мб
Выходной файл:output.txt  

Условие

Пусть имеется набор из m точек n-мерного евклидова пространства, заданных своими декартовыми координатами: (x1i, x2i, …, xni), где нижний индекс обозначает номер точки, а верхний — номер координаты.

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

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

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

Далее следует m строк, содержащих координаты точек исходного множества: (x1i, x2i, …, xni).

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

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

1 — если такой параллелепипед существует;

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

Ограничения

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

 − 104 < xki < 104, 0 < n ≤ 10, 0 < m ≤ 5 ⋅ 104

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

Входной файл (input.txt) Выходной файл (output.txt)
1
 6 3
-3056 -5013 -4706
 6423  9875  1023
-3056 -5013  1023
 6423 -5013 -4706
-3056  9875 -4706
 6423 -5013  1023
1
2
 5 2
-3170 -1400
 4950 -1400
-3170  7030
  150  3500
 4950  7030
0

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

Автор:А. Баранов   Ограничение времени:1 сек
Входной файл:input.txt   Ограничение памяти:2 Мб
Выходной файл:output.txt  

Условие

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

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

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

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

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

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

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

Ограничения

0 < (A, B) < 264

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

Входной файл (input.txt) Выходной файл (output.txt)
1
1736744720710
5067073484375
11977549798 / 34945334375
2
57295346800
351486000
163 ( 7822 / 878715 )
3
10298463668
40000000
257.4615917
4
1675223508
13509867
124

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

Автор:А. Баранов   Ограничение времени:1 сек
Входной файл:input.txt   Ограничение памяти:2 Мб
Выходной файл:output.txt  

Условие

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

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

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

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

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

Ограничения

0 ≤ A ≤ 1050, 0 < n ≤ 1000

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

Входной файл (input.txt) Выходной файл (output.txt)
1
10203756485819806252197658031528043601970
2
104116646421909761950282879573175588809976767764774752111453905887721451787880900
2
55786
17
490827381405222212342433355512086149590506305271663102056527621790991920279453696

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

Автор:А. Баранов   Ограничение времени:1 сек
Входной файл:input.txt   Ограничение памяти:2 Мб
Выходной файл:output.txt  

Условие

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

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

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

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

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

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

Ограничения

0 < |T| ≤ 5 ⋅ 104, 0 ≤ |S| ≤ 2 ⋅ 107

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

Входной файл (input.txt) Выходной файл (output.txt)
1
ABCDEF
123 AB ABCDEFABCDEF ABCDEF45ABCDEFuZ
4
2
ABCABC
ZEt AB ABCABCABCABC ABC45-ABCABCABC+
5

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

Автор:А. Баранов   Ограничение времени:1 сек
Входной файл:input.txt   Ограничение памяти:2 Мб
Выходной файл:output.txt  

Условие

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

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

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

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

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

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

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

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

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

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

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

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

Ограничения

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

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

Входной файл (input.txt) Выходной файл (output.txt)
1
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
2
TA

Задача M. Префиксные основы

Автор:А. Баранов   Ограничение времени:1 сек
Входной файл:input.txt   Ограничение памяти:2 Мб
Выходной файл:output.txt  

Условие

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

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

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

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

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

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

Ограничения

Полагается, что длина отдельно взятого слова лежит в диапазоне от 1 до 5000.

0 < n ≤ 105.

Размер входного файла не превосходит 10 МБ.

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

Входной файл (input.txt) Выходной файл (output.txt)
1
10
abcd11112345
y4141
abcd1111
abcdy
yyyy
abcdabcdabcd
A1111
A1111
11114141
AbcD
1111 5
2345 1
4141 2
a 9
bcd 7
y 6
2
10
111123abcd
y4141A
abcd1111
y4141a
abcdy
AbCdA
AbCd1111
abcd
A1111
aA
1111 4
23abcd 1
4141a 2
a 9
bcd 5
y 3

Задача N. Палиндромная сортировка

Автор:А. Баранов   Ограничение времени:1 сек
Входной файл:input.txt   Ограничение памяти:4 Мб
Выходной файл:output.txt  

Условие

Для строки S = S1S2, …, Sm определим коэффициент ее палиндромности: q[S] = k / m, где k — максимальное число позиций i в которых выполняется условие: Si  =  Sm − i + 1.

Так, например, для строк "abcba" и "abba" коэффициент палиндромности равен 100%. В то время, как для строк "abdca" и "abca" — 60% и 50% соответственно.

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

При этом для слов, обладающих одинаковой палиндромностью, порядок следования должен быть сохранен.

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

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

При этом каждое такое слово располагается в отдельной строке.

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

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

При этом полагается, что нумерация слов начинается с нуля.

Ограничения

Полагается, что длина отдельно взятого слова лежит в диапазоне от 1 до 500.

0 < n ≤ 5 ⋅ 104

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

Входной файл (input.txt) Выходной файл (output.txt)
1
10
76i3600c1
8r2xsdc44cdsxsr8
7q9wxw9q7
alf4dx3d3xdgfla
njuuiuiui0n
ierxx0es
s028338u0s
nac9ps4can
t44agihgh44t
3vtkbbkv3
2
1
3
6
8
4
7
9
5
0
2
10
15nuie40t04eiun51
l8320aa0138l
20qwzwq02
a
2e1ff1e2
4euee33e7ue4
e80t
6fesehtesif6
ml
i42iirptub
0
2
3
4
1
5
7
6
8
9

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

Автор:А. Баранов   Ограничение времени:1 сек
Входной файл:input.txt   Ограничение памяти:8 Мб
Выходной файл:output.txt  

Условие

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

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

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

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

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

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

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

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

Ограничения

n ≤ 2 ⋅ 104, m ≤ 10, 0 ≤ pi < 10

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

Входной файл (input.txt) Выходной файл (output.txt)
1
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
2
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

Задача P. Спичечные блоки

Автор:А. Баранов   Ограничение времени:1 сек
Входной файл:input.txt   Ограничение памяти:2 Мб
Выходной файл:output.txt  

Условие

Пусть имеется n спичек равной длины. Из указанных спичек необходимо собрать набор прямоугольных блоков, каждый из которых представляет собой двумерную матрицу квадратных ячеек (см. рисунок). При этом каждое ребро в таком блоке соответствует ровно одной спичке. Таким образом, полученный блок однозначно определяется своей конфигурацией [A × B], где A и B — размеры его сторон. Блоки, совпадающие с точностью до поворота, считаются одинаковыми, т.е. [A × B] = [B × A].

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

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

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

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

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

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

Ограничения

0 < n ≤ 128

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

Входной файл (input.txt) Выходной файл (output.txt)
1
23
5 1 1 1 1 1 1 1 1 1 2
3 1 1 1 2 2 2
2 1 1 1 6
2 1 2 1 5
2 1 3 1 4
2
3
 

Задача Q. Раскрытие скобок

Автор:А. Баранов   Ограничение времени:1 сек
Входной файл:input.txt   Ограничение памяти:2 Мб
Выходной файл:output.txt  

Условие

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

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

На выходе каждое такое слагаемое должно быть записано в следующем формате.

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

Каждому символу алфавита здесь должен соответствовать ровно один множитель.

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

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

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

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

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

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

Если полученное выражение тождественно равно нулю, в выходной файл выводится 0.

Ограничения

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

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

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

Входной файл (input.txt) Выходной файл (output.txt)
1
- a * b * (b+a) +b*c + b*(a + c)
2*b*c+a*b-a*b^2-a^2*b
2
 (a + b) - b -(a - b) -b 
0

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

Автор:А. Баранов   Ограничение времени:1 сек
Входной файл:input.txt   Ограничение памяти:2 Мб
Выходной файл:output.txt  

Условие

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

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

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

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

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

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

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

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

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

Ограничения

0 < (n + m) ≤ 2 ⋅ 104

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

Входной файл (input.txt) Выходной файл (output.txt)
1
8 24
00000001101111111111111111111111
000000000000000000000010
2
24 8
01000100000011001000001101000000
011000111110100111000100

Задача S. Число комнат в лабиринте

Автор:А. Баранов   Ограничение времени:1 сек
Входной файл:input.txt   Ограничение памяти:2 Мб
Выходной файл:output.txt  

Условие

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

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

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

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

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

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

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

Ограничения

0 < (n, m) ≤ 5000

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

Входной файл (input.txt) Выходной файл (output.txt)
1
xxxxxxxxx    xxx xx xxxxxxxxxxxx
xxxxxxxxx    xxx xx xxxxxxxxxxxx
xxxxxxxxx    xxx                
xxxxxxxxx    xxxxxxxxx   xxxxxxx
xxx          xxxxxxxxx   xxxxxxx
xxx   xxx    xxxxxxxxx          
xxx          xxxxxxxxx          
xxxxxx  xxx  xxxxxxxxx   xxxxxxx
xxxxxx  xxx  xxxxxxxxx   xxxxxxx
xxxxxx                   xxxxxxx
xxxxxxxxxxxxx            xxxxxxx
xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
1
2
xxx   xxx       xxxx  0000000000
xxx   xxx   xx  xxxx  0000000000
xxx   xxx   xx                  
xxxxxxxxx   xxxxxxxx  aaa    iii
            xxxxxxxx  aaa       
xxx   xxx   xxaa    aa    000iii
              aa    aa    000iii
iiiiii   aaa  aaaaaaaa    000iii
iiiiii   aaa  aaaaaaaa    000iii
000iii                          
000000   000  00000000    000000
000000   0000000000000    000000
3

Задача T. Генератор палиндромов

Автор:А. Баранов   Ограничение времени:1 сек
Входной файл:input.txt   Ограничение памяти:2 Мб
Выходной файл:output.txt  

Условие

Палиндромом называется строка символов, которая одинаково читается в обоих направлениях (слева направо и справа налево).

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

Из указанного списка требуется исключить палиндромы, лексикографический порядок которых меньше, чем у некоторой заданной строки T.
Если после этого его длина окажется больше n, лишние (с конца) палиндромы также следует удалить.

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

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

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

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

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

Ограничения

0 < |T| ≤ |S| ≤ 100,

0 < n ≤ 2 ⋅ 104

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

Входной файл (input.txt) Выходной файл (output.txt)
1
abcbac
aca
15
aca
acbbca
acbca
acca
b
baab
bab
bacab
baccab
bb
bcaacb
bcacb
bcb
bccb
c
2
123243
21a
50
22
23132
232
2332
23432
242
3
313
32123
3223
323
32423
33
343
4

1.328s 0.023s 53