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

Условие

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

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

Условие

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

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

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

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

Условие

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

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

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

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

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

Условие

Пусть имеются два каталога 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"

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

Условие

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

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

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

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

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

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

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

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

Входной файл "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

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

Условие

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