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

Условие

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

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

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

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

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

Ограничения

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

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

10203756485819806252197658031528043601970
2

104116646421909761950282879573175588809976767764774752111453905887721451787880900

55786
17

490827381405222212342433355512086149590506305271663102056527621790991920279453696

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

Условие

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

Пусть имеется некоторая бинарная последовательность (состоящая из нулей и единиц), разбитая на блоки фиксированной длины. При этом заранее известно, что каждый такой блок содержит в себе ровно 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

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

Условие

Пусть имеется многочлен, представленный в следующем виде: 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

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

Условие

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

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

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

В заголовке входного файла "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

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

Условие

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

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

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

Задача F. Частотный словарь ≡

Условие

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

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

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

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

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

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

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

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

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

Ограничения

Полагается, что длина отдельно взятого слова составляет не более 10 символов.

Число уникальных слов, формирующих словарь, не превосходит 5 ⋅ 10⁴.

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

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

This is the house that Jack built.

This is the cheese that lay in the house that Jack built.

This is the rat that ate the cheese
That lay in the house that Jack built.

This is the cat that chased the rat
That ate the cheese that lay in the house that Jack built.

This is the dog that worried the cat
That chased the rat that ate the cheese
That lay in the house that Jack built.

This is the cow with the crumpled horn
That tossed the dog that worried the cat
That chased the rat that ate the cheese
That lay in the house that Jack built.

This is the maiden all forlorn
That milked the cow with the crumpled horn
That tossed the dog that worried the cat
That chased the rat that ate the cheese
That lay in the house that Jack built.

This is the man all tattered and torn
That kissed the maiden all forlorn
That milked the cow with the crumpled horn
That tossed the dog that worried the cat
That chased the rat that ate the cheese
That lay in the house that Jack built.

This is the judge all shaven and shorn
That married the man all tattered and torn
That kissed the maiden all forlorn
That milked the cow with the crumpled horn
That tossed the dog that worried the cat
That chased the rat that ate the cheese
That lay in the house that Jack built.

This is the rooster that crowed in the morn
That woke the judge all shaven and shorn
That married the man all tattered and torn
That kissed the maiden all forlorn
That milked the cow with the crumpled horn
That tossed the dog that worried the cat
That chased the rat that ate the cheese
That lay in the house that Jack built.

This is the farmer sowing his corn
That kept the rooster that crowed in the morn
That woke the judge all shaven and shorn
That married the man all tattered and torn
That kissed the maiden all forlorn
That milked the cow with the crumpled horn
That tossed the dog that worried the cat
That chased the rat that ate the cheese
That lay in the house that Jack built.

This is the horse and the hound and the horn
That belonged to the farmer sowing his corn
That kept the rooster that crowed in the morn
That woke the judge all shaven and shorn
That married the man all tattered and torn
That kissed the maiden all forlorn
That milked the cow with the crumpled horn
That tossed the dog that worried the cat
That chased the rat that ate the cheese
That lay in the house that Jack built.

all 15
and 11
ate 10
belonged 1
built 12
cat 9
chased 9
cheese 11
corn 2
cow 7
crowed 3
crumpled 7
dog 8
farmer 2
forlorn 6
his 2
horn 8
horse 1
hound 1
house 12
in 14
is 12
jack 12
judge 4
kept 2
kissed 5
lay 11
maiden 6
man 5
married 4
milked 6
morn 3
rat 10
rooster 3
shaven 4
shorn 4
sowing 2
tattered 5
that 81
the 90
this 12
to 1
torn 5
tossed 7
with 7
woke 3
worried 8

Задача G. Библиографический каталог ≡

Условие

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

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

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

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

<имя_автора> <название_книги>

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

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

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

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

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

Ограничения

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

0 < n ≤ 2 ⋅ 10⁴

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

12
Vanya ABC
Danya XYZ
Anton GIT
Vitya Xyz
Daria git
Vahob Git
other 000
vanya 123
vanya abc
danya END
danya 123
vanya End

7
vanya
danya
anton
vitya
daria
vahob
other

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

6
abc 4
xyz 3
git 0
000 2
123 1
end 1

Задача H. Слияние каталогов ≡

Условие

Пусть имеются два каталога dir1 и dir2, содержащие некоторые файлы и подкаталоги (папки). Требуется выполнить их слияние, включающее в себя набор следующих шагов:

• выполнить удаление всех файлов и подкаталогов, существующих в каталоге dir2, но отсутствующих в каталоге dir1;
• выполнить копирование файлов/подкаталогов, существующих в каталоге dir1, если они отсутствуют в dir2;
• оставшиеся файлы из каталога dir2 следует заменить более новыми, взятыми из каталога dir1 (под "более новыми" здесь имеются в виду файлы, время последнего изменения которых больше, чем у исходных).

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

• cpy "name" — запрос на копирование файла/подкаталога с заданным именем name из каталога dir1 в dir2
  (при этом каталог копируется вместе со всем своим содержимым, включая его подкаталоги);
• del "name" — запрос на удаление файла/подкаталога с заданным именем из каталога dir2.

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

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

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

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

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

"name":time, где name — имя элемента; time — время последнего изменения (представляет собой целое число в диапазоне от 0 до 2⁶⁴ − 1).

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

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

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

Ограничения

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

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

Общее количество элементов в каждом из каталогов (включая содержимое всех его подкаталогов) не превосходит 10⁴.

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

("sub1":10325 ("fid1":1094, "fid0":3217,
 "sub2":4905  ("fid3":5600)
              ),
 "sub3":24601 ()
)

("sub1":10325 ("fid1":1094, "fid2":3210,
 "sub2":4905  ("fid3":5000,
               "fid4":1249)
              ),
 "sub3":30509
)

del "sub1/fid2"
cpy "sub1/fid0"
del "sub1/sub2/fid4"
cpy "sub1/sub2/fid3"
del "sub3"
cpy "sub3"

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

Условие

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

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

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

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

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

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

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

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

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

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

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

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

Ограничения

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

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

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

- a * b * (b+a) +b*c + b*(a + c)

2*b*c+a*b-a*b^2-a^2*b

 (a + b) - b -(a - b) -b 

0

Задача J. Производная функции ≡

Условие

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

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

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

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

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

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

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

Ограничения

Полагается, что исходная функция не содержит синтаксических ошибок.

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

sin(x^3) -cos(x* exp(x / exp(x^ 2)))

3*x^2*cos(x^3)+(1+x*((1-2*x^2)/exp(x^2)))*exp(x/exp(x^2))*sin(x*exp(x/exp(x^2)))

x^5 - x * (2.0 * x^ 4 - x * x^3) + x

1