Задача A. Форум ≡

Условие

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

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

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

Первая строка входного файла содержит целое число N — количество сообщений в форуме. Следующие строки содержат описание сообщений в хронологическом порядке.

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

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

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

Ограничения

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

7
0
Олимпиада по информатике
Скоро третья командная олимпиада?
0
Новая компьютерная игра
Вышла новая крутая игра!
1
Она пройдет 24 ноября
1
В Санкт-Петербурге и Барнауле
2
Где найти?
4
Примет участие более 50 команд
6
Интересно, какие будут задачи

Олимпиада по информатике

Задача B. Поезда ≡

Условие

В связи с увеличившимся числом аварий на железнодорожной трассе "Нью-Васюки-Петербург" руководство железнодорожной компании решило изменить график движения поездов. Тщательный анализ состояния полотна установил, что оптимальным является следующий график движения: сначала T₁ минут поезд идет со скоростью V₁ метров в минуту, затем T₂ минут со скоростью V₂ м/мин, ..., наконец, T_N минут со скоростью V_N м/мин. В течение интервала T_i (1 ≤ i ≤ N) поезд может стоять.

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

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

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

Ограничения

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

1000
4
10 0
30 80
15 0
20 100

27.5

Задача C. Монстры ≡

Условие

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

Рисунок 1. Монстры на столе для экспериментов

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

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

Первая строка входного файла содержит числа M и N - размеры лабораторного стола. Следующая строка содержит число K - количество монстров. Следующие K строк содержат описания монстров - два целых числа и один символ из множества {N, E, S, W} - начальные координаты и направление соответствующего монстра (соответствие направлений и координат приведено на рисунке 1). Символ отделен от чисел ровно одним пробелом.

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

Ограничения

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

8 5
4
4 4 S
6 2 W
6 3 N
6 4 S

13