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

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

Условие

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

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

Первая строка входного файла "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. Ловушка для подвижных частиц

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

Условие

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

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

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

Определим кольцо, как область, заключенную между двумя окружностями с общим центром (x0, y0) и разными радиусами: r2 > r1 > 0. В этом случае исходное множество частиц можно условно разбить на три группы:

  1. частицы, попадающие во внутренний круг с центром в точке (x0, y0) и радиусом r1 > 0;
  2. частицы, заключенные между двумя окружностями с радиусами r1 и r2;
  3. частицы, лежащие за пределами внешнего круга с радиусом r2 > r1.

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

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

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

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

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

В первой строке входного файла "input.txt" содержатся параметры расчетной области: x0, y0, r1, r2. Во второй строке указано значение T, задающее длину временного интервала, и число его подынтервалов m. Далее следует натуральное число n и последовательность из 4 × n вещественных чисел, задающих начальные координаты и скорости каждой из частиц: xi, yi, ui, vi, где i = 1, 2, …, n.

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

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

Ограничения

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

2 ≤ r1 ≤ (r2 − 2) ≤ 10, 0 < T ≤ 20, 0 < m ≤ 10,

ui2+vi2 ≤ 25, 0 < n ≤ 4000

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

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

Задача E. Треугольник в параллелепипеде

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

Условие

Пусть имеется параллелепипед со сторонами, параллельными осям координат: D = { (x, y, z): xmin ≤ x ≤ xmax, ymin ≤ y ≤ ymax, zmin ≤ z ≤ zmax} и некоторый треугольник T, заданный координатами своих вершин: (x1, y1, z1), (x2, y2, z2), (x3, y3, z3).

Требуется определить площадь той части треугольника T, которая имеет общие точки с параллелепипедом D.

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

В начале входного файла "input.txt" записаны координаты двух наиболее удаленных вершин параллелепипеда: (xmin, ymin, zmin), (xmax, ymax, zmax).

Далее следуют координаты вершин треугольника: (x1, y1, z1), (x2, y2, z2), (x3, y3, z3).

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

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

Ограничения

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

xmin ≤ xmax, ymin ≤ ymax, zmin ≤ zmax.

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

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

-1.25000  0.56000  1.28090
-1.30000 -1.29010 -0.75000
 0.60790 -1.30700  1.30600
0.97386
2
-1.50000 -1.50000  1.00000
 0.50000  0.00000  1.50000

-3.70980  0.67000  3.20000
-4.60000 -1.86010  3.80250
 1.00000 -1.25000  4.10900
0.00000

Задача F. Пересечение двух пластин

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

Условие

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

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

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

В начале входного файла "input.txt" хранятся вещественные координаты точек, задающих 1-ю из имеющихся пластин: (x1, y1, z1), (x2, y2, z2) и (x3, y3, z3). Далее следуют координаты точек, задающих 2-ю пластину: (x4, y4, z4), (x5, y5, z5) и (x6, y6, z6).

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

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

1 — если заданные пластины пересекаются;

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

Ограничения

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

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

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

Входной файл (input.txt) Выходной файл (output.txt)
1
 1.37001 -8.96720 -5.08104
-9.09250 -0.15130 -8.70300
 9.07213 -5.40160  4.09015
 7.58011  8.42032  9.03280
-1.34060  2.07613 -5.17640
 5.04500  7.18045  1.03409
1
2
 0.37001 -8.76004 -5.38004
-4.09250  0.20150  7.10350
 5.07011 -5.40160  3.59182
 8.94060  7.42032 -0.33687
 1.50300  8.07600  5.74690
-9.04500  3.02401  1.00830
0

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

Автор:А. Баранов   Ограничение времени: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

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

Автор:А. Баранов   Ограничение времени: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

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

Автор:А. Баранов   Ограничение времени: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

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

Автор:А. Баранов   Ограничение времени: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

Problem K. Directory synchronization

Author:A. Baranov   Time limit:2 sec
Input file:input.txt   Memory limit:256 Mb
Output file:output.txt  

Statement

Consider the directory that contains files. Names of these files are composed from Latin letters (uppercase A-Z and lowercase a-z letters are distinct), digits, such characters as '-' (ASCII 45), '.' (ASCII 46) and spaces (ASCII 32). Different files have different names.

Initial content of any file is unique. In future it can not be changed, but it can be copied to a new file.

There is need to periodically synchronize the local version of this directory with its backup copy that is placed on remote server. In this case the previous version of the remote directory must be updated to the current state with minimal computational costs.

For this purpose all operations that are performed in the local directory are stored to in a special log, in historical order. This log contains records in following forms:

It is known that these operations cause error if:

To update of the remote directory, we must apply similar operations to it. In this case each of them has a certain cost: for mov and del it is 1, cost of cpy is 10.

Also we assume that operation new means to copy a file from the local directory to remote server and has cost is 100.

Your program must, given the initial state of remote directory and set of records of the log, obtain sequence of the operations with minimal total cost that allow to make update of the backup copy to the current state. These operations must not cause errors.

Special file name "~" (ASCII 126) is considered acceptable by remote server, but is not used by operations in the log. It is recommended to use this name for temporary file copies.

Input file format

Input file contains integer N — initial number of files in the directory, followed by the N file names enclosed in double quotes, one name per line.

After that, input file contains integer M — number of the records of the log, followed by M log records, one record per line.

All file names are enclosed in double quotes.

Output file format

Output file must contain integer L — number of the operations, followed by L operations in the same format as log records, one operation per line.

All file names must be enclosed in double quotes.

Constraints

File names have length from 1 to 16 characters. Operations in the log do not cause errors.

0 ≤ N, M ≤ 104

Sample tests

No. Input file (input.txt) Output file (output.txt)
1
5
"BaNaNa-145"
"Example-01"
"MyMusic-03"
"MyGame.exe"
"UNIT.1.pas"

10
mov "MyMusic-03" "BestMusic.mp3"
mov "MyGame.exe" "F0"
mov "BaNaNa-145" "MyMusic-03"
del "Example-01"
cpy "UNIT.1.pas" "UNIT.2.pas"
del "UNIT.1.pas"
mov "F0" "BaNaNa-145"
new "x2"
mov "BestMusic.mp3" "MyGame.exe"
new "UNIT.1.pas"
8
mov "BaNaNa-145" "~"
mov "MyGame.exe" "BaNaNa-145"
mov "MyMusic-03" "MyGame.exe"
mov "~" "MyMusic-03"
del "Example-01"
mov "UNIT.1.pas" "UNIT.2.pas"
new "x2"
new "UNIT.1.pas"
2
5
"BaNaNa-145"
"Example-01"
"MyMusic-03"
"MyGame.exe"
"UNIT.1.pas"

10
mov "BaNaNa-145" "BaNaNa-360"
cpy "MyMusic-03" "M0"
cpy "BaNaNa-360" "NaN.InF"
mov "NaN.InF" "BaNaNa-145"
new "x2"
del "BaNaNa-360"
mov "M0" "Music.mp3"
del "MyMusic-03"
mov "Music.mp3" "MyMusic-03"
del "x2"
0

Задача L. Треугольные конфигурации

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

Условие

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

Примечание

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

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

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

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

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

Ограничения

Гарантируется, что никакие две прямые не совпадают между собой.

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

104 ≤ (axi, ayi, bxi, byi) ≤ 104, 3 ≤ n ≤ 300

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

Входной файл (input.txt) Выходной файл (output.txt)
1
5
  0 -20  15 -20
-10  10  35 -35
  0   0   0 -10
-10   0  30   0
-20   0   0  20
3
2
5
-10   0   0 -20
-20 -10 -10 -30
  0   0  10  24
  0  10  10 -10
-10   0   0  24
0

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

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

Задача N. В помощь курьерам!

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

Условие

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

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

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

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

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

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

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

Ограничения

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

2 ≤ n ≤ 200, 1 ≤ m ≤ (n ⋅ (n − 1)) / 2,

0 ≤ (ai, bi) < n, 0 < wi ≤ 10

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

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

Задача O. Водопроводная сеть

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

Условие

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

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

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

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

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

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

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

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

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

Ограничения

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

2 ≤ n ≤ 1000, 1 ≤ m ≤ (n ⋅ (n − 1)) / 2,

0 ≤ (ai, bi) < n, 0 < wi ≤ 10

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

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

Задача P. Сжатое дерево

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

Условие

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

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

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

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

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

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

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

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

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

Ограничения

Полагается, что каждый узел имеет не более 10 потомков. При этом общее число узлов никогда не превосходит 3 ⋅ 105.

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

Входной файл (input.txt) Выходной файл (output.txt)
1
a 2
b 2
a 0
a 0
c 1
b 2
a 0
a 0
1 5
6 7
2
c 3
b 1
a 0
c 1
b 2
e 0
c 0
b 0
 

Задача Q. Распространение примеси

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

Условие

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

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

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

Известно, что при прохождении через k-й промежуточный узел концентрация примеси изменяется на аддитивную константу Fk. Процент примеси, пропускаемый через ребро, направленное из узла с номером k в узел с номером l, определяется коэффициентом Wk l.

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

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

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

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

Вначале идет пара натуральных значений n и m — число вершин и ребер в таком графе. За ними следует набор из m ребер, каждое из которых задается тремя значениями: k и l — номера вершин, которые оно соединяет; Wk l — весовой коэффициент. При этом полагается, что нумерация вершин начинается с нуля.

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

Далее следует список, в котором каждому промежуточному узлу с номером k ставится в соответствие вещественная константа Fk, а каждому конечному узлу с номером j — значение Yj.

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

Если задача имеет единственное решение, в выходной файл "output.txt" выводится строка 'SOLUTION:', за которой следует список из номеров входных узлов i и соответствующих им значений Xi, указанных с точностью до 5-го знака после запятой.

В противном случае, выходной файл должен содержать строку 'INFINITY!'.

Ограничения

Гарантируется, что точное решение всегда существует и удовлетворяет следующим соотношениям: 0 ≤ Xi ≤ 10.

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

Число ребер, исходящих из одной вершины, не превосходит 10, а их суммарный вес равен 1.

0 ≤ Fk ≤ 10, 2 ≤ n ≤ 1000, 0 < m.

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

Входной файл (input.txt) Выходной файл (output.txt)
1
10 9
0 3 1.00000
1 6 0.75000
1 4 0.25000
4 6 1.00000
6 3 0.50000
6 7 0.50000
2 5 1.00000
5 8 0.50000
5 9 0.50000

4 2.50480
5 1.39000
6 0.75630

3 5.30580
7 3.41550
8 1.91030
9 1.91030
SOLUTION:
0 1.89030
1 3.56990
2 2.43060
2
8 7
0 3 0.75000
0 4 0.25000
3 5 0.50000
3 6 0.50000
4 7 1.00000
1 4 1.00000
2 4 1.00000

3 1.36070
4 2.04590

5 2.71740
6 2.71740
7 7.41445
INFINITY!

Задача R. Коррекция фотоснимков

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

Условие

Матрица фотоаппарата представляет собой прямоугольную таблицу размерности [n × m], состоящую из светочувствительных элементов (ячеек). В момент съемки каждой ячейке такой таблицы ставится в соответствие вещественное значение Xi j, указывающее ее состояние (интенсивность).

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

Коэффициент влияния каждой такой ячейки на полученное значение равен 1 / (2l ⋅ Nl), где l — номер содержащего ее слоя, Nl — число ячеек в l-м слое.

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

Для некоторой заданной матрицы Y, полученной в результате измерений, и радиуса воздействия k требуется восстановить исходные значения Xi j.

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

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

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

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

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

Ограничения

0 < n ⋅ m ≤ 40000, 0 < k ≤ 6

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

Входной файл (input.txt) Выходной файл (output.txt)
1
9 6 3
5.37440 1.87298 5.08681 5.09439 3.57315 3.55082
4.84972 5.78076 5.88345 5.75286 2.34798 2.47103
3.86090 6.57539 3.56487 6.79445 2.32794 1.16099
2.87753 3.34932 6.59350 5.05354 3.07699 2.10780
5.02344 5.31951 6.03288 2.75002 2.86035 3.99470
5.33926 2.95632 5.48640 4.94406 6.01522 1.82400
1.96623 4.91699 6.77083 6.70678 3.62880 1.38931
2.07507 5.79116 6.66805 4.14477 5.60571 1.57956
2.96721 1.63348 2.82736 3.08427 4.54261 3.77225
4.54131 0.26822 3.63874 3.75977 2.43927 2.94755
3.49550 3.85922 3.75414 3.92569 0.66599 1.63885
2.38207 4.58287 1.01207 4.86523 0.65718 0.26808
1.29046 1.08997 4.35343 3.08341 1.48435 1.14364
3.72711 3.21447 3.97145 0.44224 1.13006 2.95406
4.03403 0.67137 3.22229 2.67277 4.43113 0.66156
0.62032 2.92664 4.52078 4.37446 1.85234 0.18678
1.01331 4.23441 4.76965 2.02538 4.09963 0.42683
2.29344 0.39009 1.51680 1.64687 3.47349 3.00115

1.874s 0.024s 59