Задача A. Океанариум ≡

Условие

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

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

Например, если в первый раз Петя увидел трёх гуппи и одного вуалехвоста, а во второй раз — четырёх вуалехвостов, то всего в аквариуме не менее 7 рыбок.

Рекомендуется рассмотреть частичные решения

• N = 1,
• каждый листок содержит ровно одно название рыбки.

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

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

Ограничения

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

1
2
Carassius auratus
Poecilia reticulata

2

3
5
Lionhead
Pompom
Pearlscale
Pearlscale
Lionhead
2
Pompom
Pompom
5
Lionhead
Lionhead
Ryukin
Pearlscale
Lionhead

8

Задача B. Репликация ≡

Условие

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

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

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

Рекомендуется рассмотреть частичные решения

• N ≤ 100

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

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

Ограничения

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

3 3
1 2
1 2
2 3

2
1
0

3 3
1 2
1 3
2 3

1
2
1

Задача C. Физика Хоттабыча ≡

Условие

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

Теперь энергия материальной точки в определённый момент времени будет равна E, если в радиусе L метров от неё найдётся ещё хотя бы одна точка, либо P, если таких точек нет.

На бесконечной плоскости имеется K материальных точек. Хоттабыч знает начальное положение каждой точки (x_i; y_i) и их скорости вдоль осей OX и OY — u_i и v_i. Таким образом, i-ая точка в момент времени t будет иметь координаты (x_i + u_i*t; y_i + v_i*t).

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

Рекомендуется рассмотреть частичные решения

• K ≤ 2

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

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

Ограничения

1 ≤ K ≤ 1000

0 ≤ E, P, L, T ≤ 1000

−1000 ≤ x_i, y_i, u_i, v_i ≤ 1000

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

1 20 100 0.000 0.000
0 0 0 0

100

3 20 15 1.000 531.715
0 0 0 0
1 1 1 0
2 2 0 -1

55

4 1000 992 0.001 3.133
10 10 -70  -70 
20 20 -140 -140 
30 30 -210 -210 
40 40 -280 -280

4000

Задача D. Калейдоскоп ≡

Условие

Назовём калейдоскопом размера N ASCII-изображение, состоящее из 2 × N + 3 строк по 2 × N + 3 символа. Центральная горизонталь, центральная вертикаль, обе большие диагонали калейдоскопа должны состоять из символов '#' (ASCII 35). Восемь сегментов, на которые калейдоскоп разбивается этими четырьмя осями, должны быть заполнены латинскими буквами таким образом, чтобы изображение было симметрично относительно осей.

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

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

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

Ограничения

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

5
a
bc
def
ghij
klmno

#abdgk#kgdba#
a#cehl#lhec#a
bc#fim#mif#cb
def#jn#nj#fed
ghij#o#o#jihg
klmno###onmlk
#############
klmno###onmlk
ghij#o#o#jihg
def#jn#nj#fed
bc#fim#mif#cb
a#cehl#lhec#a
#abdgk#kgdba#