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

Автор:?
Входной файл: monsters.in   Ограничение времени:2 сек
Выходной файл: monsters.out   Ограничение памяти:200 Мб

Условие

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

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

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

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

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

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

В выходной файл выведите единственное число - количество клеток стола, на которых побывают монстры.

Ограничения

1 ≤ N, M ≤ 106, 1 ≤ K ≤ 103,

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

Входной файл (monsters.in) Выходной файл (monsters.out)
1
8 5
4
4 4 S
6 2 W
6 3 N
6 4 S
13

Задача B. Форум

Автор:?
Входной файл: forum.in   Ограничение времени:2 сек
Выходной файл: forum.out   Ограничение памяти:200 Мб

Условие

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

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

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

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

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

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

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

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

Ограничения

1 ≤ N ≤ 1000, Длина всех сообщений не превышает 100 символов.

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

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

Задача E. Дробь в LATeX-е

Автор:?
Входной файл: frac.in   Ограничение времени:2 сек
Выходной файл: frac.out   Ограничение памяти:200 Мб

Условие

Издательская система LATeX предназначена для верстки сложных научно-технических текстов с большим количеством формул. Исходный файл для системы LATEX пишется на языке TEX и представляет собой текст документа, в который включены специальные символы и команды. Специальные символы и команды описывают размещение текста, в частности в математических формулах. Команда представляет собой последовательность латинских букв (регистр важен), перед которой стоит символ "\". Так, команда \frac предназначена для описания дроби, в которой числитель расположен над знаменателем. Рассмотрим простейшую структуру команды \frac.

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

Дадим также формальное определение выражения для нашей задачи:

Здесь вертикальная черта | означает "или", заключенная в квадратные скобки часть может отсутствовать, а символы, записаные в кавычках обозначают самих себя. Печатный символ - любой символ с ASCII кодом от 32 (пробел) до 127. Например, выражение записывается на языке TEX как

\frac{a+b}{d+1}+\frac ax -\frac 2 {2+\frac{3}{y}}

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

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

\frac{a+b}{\frac cd}+\frac{\frac ef}{g+h}
\frac{a+b+c}{\frac{\frac de}{g+h}}+\frac{i+j+k}{\frac{l+m}{\frac no}}

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

В первой строке находятся целые положительные числа S и D. Следующая строка содержит описание формулы на TEX-е, длина строки не более 200 символов. Гарантируется, что формула синтаксически корректна, то есть фигурные скобки образуют правильную скобочную последовательность и строка содержит только печатные символы. Все символы "\", встречающиеся в строке относятся к некоторой командной последовательности (не обязательно \frac), можете считать, что все прочие командные последовательности задают символы, высота которых равна S. Числитель и знаменатель каждой дроби содержат хотя бы по одному символу, вся формула содержит хотя бы один символ.

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

Выведите в выходной файл единственное число — высоту формулы.

Ограничения

1 ≤ S, D ≤ 10000

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

Входной файл (frac.in) Выходной файл (frac.out)
1
10 2
\frac{a+b}{d+1}+\frac ax -\frac 2 {2+\frac{3}{y}}
34
2
10 2
no fractions here
10
3
10 2
\frac        {\alpha}          {\beta+\sin{2+x}}
22
4
10 2
\cos{\frac{\alpha}b}
22
5
10 2
\frac a  {sin{a}}
22
6
10 2
\frac{a+b}{\frac cd}+\frac{\frac ef}{g+h}
46
7
10 2
\frac{a+b+c}{\frac{\frac de}{g+h}}+\frac{i+j+k}{\frac{l+m}{\frac no}}
46

0.042s 0.004s 21