Темы
    Информатика(2609 задач)
---> 9 задач <---
Страница: 1 2 >> Отображать по:
#536
  
Источники: [ Командные олимпиады, ВКОШП, 2002, Задача A ]
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
64 megabytes
На прямоугольной таблице находятся монстры. Каждый монстр характеризуется координатами и направлением движения. Монстр идет до конца поля и оставляет следы. Необходимо определить суммарное количество испачканных клеток.

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

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

Входные данные

В первой строке вводятся числа $M$ и $N$ - размеры лабораторного стола (1 <= $M$, N <= $10^6$). В следующей строке задается число $K$ - количество монстров (0 <= $K$ <= $10^3$). Следующие $K$ строк содержат описания монстров - два целых числа и один символ из множества {$N$, $E$, $S$, $W$} - начальные координаты и направление соответствующего монстра (соответствие направлений и координат приведено на рисунке 1). Символ отделен от чисел ровно одним пробелом.

Выходные данные

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

Пояснение к примеру

Пример соответствует расположению монстров, приведенному на рисунке 1.монстры.

Примеры
Входные данные
8 5
4
4 4 S
6 2 W
6 3 N
6 4 S
Выходные данные
13

#537
  
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
64 megabytes
Задано описание форума. Новая тема является ответом на тему 0, а для сообщения указывается, на какое сообщение оно является ответом. Необходимо определить тему с наибольшим количеством ответов.

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

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

Входные данные

В первой строке вводится целое число N - количество сообщений в форуме (1 <= $N$ <= 1000). Следующие строки содержат описание сообщений в хронологическом порядке.

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

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

Длина каждого из сообщений не превышает 100 символов.

Выходные данные

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

Примеры
Входные данные
2
0
topic 1
body of message 1
0
topic 2
body of message 2
Выходные данные
topic 1
Входные данные
2
0
topic 1
body of message 1
1
body of message 2 being the reply to message 1
Выходные данные
topic 1
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
64 megabytes
Необходимо найти три наиболее удаленные вершины дерева. Удаленность считается как сумма расстояний между парами вершин.

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

Недавно президента этой страны заинтересовал вопрос: какие три города являются наиболее удаленными друг от друга. А именно, назовем взаимной удаленностью друг от друга трех городов $A$, $B$ и $C$ минимальное количество дорог, которое необходимо использовать, чтобы доехать от $A$ до $B$, затем от $B$ до $C$ и затем от $C$ до $A$ (при этом разрешается использовать одну и ту же дорогу в различных путешествиях).

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

Например, для пяти городов, соединенных дорогами так, как это показано на рисунке 1, три наиболее удаленных друг от друга города - это города 1, 2 и 5 (взаимная удаленность равна 2 + 3 + 3 = 8), а для городов на рисунке 2 - это любые три города, выбранные из множества {1, 2, 4, 5} (удаленность 2 + 2 + 2 = 6).

Входные данные

В первой строке вводится число $N$ - количество городов (3 <= $N$ <= 1000). Следующие N строк содержат описания городов. Описание i-го города сначала содержит $K_i$ - количество городов, с которыми он соединен дорогами (1 <= $K_i$ < $N$), а затем $K_i$ чисел - номера городов, с которыми он соединен. Гарантируется, что входные данные корректны - то есть если есть дорога из города A в город B, то есть и дорога из города B в город A, причем для всех пар городов выполняется свойство, указанное в условии задачи.

Выходные данные

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

Примеры
Входные данные
5
1 3
1 3
3 1 2 4
2 3 5
1 4
Выходные данные
5 2 1
Входные данные
5
1 3
1 3
4 1 2 4 5
1 3
1 3
Выходные данные
1 2 4
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
64 megabytes
Необходимо разбить выпуклый многоугольник с целыми координатами на треугольники с вершинами в целых точках и площадью 1/2. Формула Пика.

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

Входные данные

В первой строке вводится число $N$ - количество вершин многоугольника (1 <= $N$ <= 10). Следующие $N$ строк содержат координаты вершин многоугольника в порядке обхода их по часовой стрелке. Все координаты - целые неотрицательные числа, не превышающие 10. Никакие три последовательные вершины многоугольника не лежат на одной прямой.

Выходные данные

Если выполнить разбиение указанным образом невозможно, выведите единственное число - 0. В противном случае выведите несколько строк, содержащих по 6 чисел каждая. Количество строк должно быть равно количеству треугольников в найденном разбиении. Числа в каждой строке должны представлять собой координаты вершин соответствующего треугольника - $x_1$, $y_1$, $x_2$, $y_2$, $x_3$, $y_3$. Площадь каждого треугольника должна быть 1/2. Порядок перечисления треугольников и вершин в каждом из треугольников может быть произвольным. Если допустимых разбиений несколько, выведите любое

Примеры
Входные данные
4
0 0
0 2
2 2
1 0
Выходные данные
2 2 0 1 1 2
0 1 0 2 1 2
0 0 0 1 1 1
0 1 2 2 1 1
2 2 1 0 1 1
1 0 0 0 1 1
#540
  
Источники: [ Командные олимпиады, ВКОШП, 2002, Задача E ]
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
64 megabytes
Задано описание команды TeX \frac (дробь). По данному TeX выражению необходимо подсчитать его высоту.

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

Команда \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$ (1 <= $S$, $D$ <= 10000). Следующая строка содержит описание формулы на TEX-е, длина строки не более 200 символов. Гарантируется, что формула синтаксически корректна, то есть фигурные скобки образуют правильную скобочную последовательность и строка содержит только печатные символы. Все символы "", встречающиеся в строке относятся к некоторой командной последовательности (не обязательно \frac), можете считать, что все прочие командные последовательности задают символы, высота которых равна $S$. Числитель и знаменатель каждой дроби содержат хотя бы по одному символу, вся формула содержит хотя бы один символ.

Выходные данные

Выведите единственное число - высоту формулы.

Примеры
Входные данные
10 2
\frac{a+b}{d+1}+\frac ax -\frac 2 {2+\frac{3}{y}}
Выходные данные
34
Входные данные
10 2
no fractions here
Выходные данные
10
Входные данные
10 2
\frac        {\alpha}          {\beta+\sin{2+x}}
Выходные данные
22
Входные данные
10 2
\cos{\frac{\alpha}b}
Выходные данные
22
Входные данные
10 2
\frac a  {sin{a}}
Выходные данные
22
Входные данные
10 2
\frac{a+b}{\frac cd}+\frac{\frac ef}{g+h}
Выходные данные
46
Входные данные
10 2
\frac{a+b+c}{\frac{\frac de}{g+h}}+\frac{i+j+k}{\frac{l+m}{\frac no}}
Выходные данные
46

Страница: 1 2 >> Отображать по:
Выбрано
:
Отменить
|
Добавить в контест