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

Автор:А. Баранов   Ограничение времени:1 сек
Входной файл:input.txt   Ограничение памяти:256 Мб
Выходной файл: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

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

Автор:А. Баранов   Ограничение времени:1 сек
Входной файл:input.txt   Ограничение памяти:256 Мб
Выходной файл: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

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

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

Условие

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

Требуется привести его к каноническому виду: A0 + A1 ⋅ x + …  + An ⋅ xn.

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

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

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

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

Ограничения

2 ≤ p < 264, 0 ≤ Ci < p, 0 ≤ n ≤ 500

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

Входной файл (input.txt) Выходной файл (output.txt)
1
100 5
2
13
4
37
6
29
48
68
90
90
22
2
2
2 4
1
0
1
0
1
0
0
1
0
1

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

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

Условие

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

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

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

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

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

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

Ограничения

0 < n ≤ 106, 0 < Ai ≤ 109

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

Входной файл (input.txt) Выходной файл (output.txt)
1
8

23
31
742
4
5
84
6
19
6
2
5

12
145
7
94
2
0

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

Автор:А. Баранов   Ограничение времени:1 сек
Входной файл:input.txt   Ограничение памяти:256 Мб
Выходной файл: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

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

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

Условие

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

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

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

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

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

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

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

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

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

Ограничения

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

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

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

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

Входной файл (input.txt) Выходной файл (output.txt)
1
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. Библиографический каталог

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

Условие

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

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

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

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

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

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

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

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

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

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

Ограничения

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

0 < n ≤ 2 ⋅ 104

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

Входной файл (input.txt) Выходной файл (output.txt)
1
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. Слияние каталогов

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

Условие

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

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

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

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

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

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

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

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

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

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

Ограничения

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

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

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

Входной файл (input.txt) Выходной файл (output.txt)
1
("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. Раскрытие скобок

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

Условие

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

В указанном выражении требуется раскрыть скобки и выполнить приведение подобных слагаемых. На выходе каждое такое слагаемое должно быть записано в следующем формате: C * A[1]^p[1] * A[2]^p[2] * ... * A[26]^p[26],

где C — некоторый целочисленный коэффициент (может быть опущен, если он равен единице);
A[i] — множитель, соответствующий i-му символу алфавита;
p[i] — целое число, определяющее его степень.

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

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

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

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

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

Условие

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

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

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

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

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

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

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

Ограничения

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

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

Входной файл (input.txt) Выходной файл (output.txt)
1
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)))
2
x^5 - x * (2.0 * x^ 4 - x * x^3) + x
1

0.352s 0.011s 31