Страница: 1 Отображать по:
#537
Форум
  
Источники: [ Командные олимпиады, ВКОШП, 2002, Задача B ]
ограничение по времени на тест
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
#543
Военная сортировка
  
Источники: [ Командные олимпиады, ВКОШП, 2002, Задача H ]
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
64 megabytes
Требуется упорядочить числа от 1 до N. Разрешается менять только соседние числа и нельзя переставлять число, которое уже стоит на своем месте.

Фирма Macrohard получила заказ от армии одной страны на реализацию комплекса программного обеспечения для нового суперсекретного радара. Одной из наиболее важных подпрограмм в разрабатываемом комплексе является процедура сортировки.

Однако в отличие от обычной сортировки, эта процедура должна сортировать не произвольный массив чисел, который передается ей на вход, а специальный заранее заданный массив из \(N\) чисел, в котором записана некоторая фиксированная перестановка чисел от 1 до \(N\), и кроме того, ни одно число в нем изначально не находится на своем месте (то есть на позиции с номером i изначально не находится число \(i\)).

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

Например, если массив из 6 элементов в некоторый момент имеет вид <2, 1, 3, 6, 4, 5>, то можно поменять местами 1 и 2, 6 и 4 или 4 и 5, а менять местами 1 и 3 или 3 и 6 нельзя, поскольку число 3 находится на своем месте (на позиции с номером 3).

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

Подсказка

Найти такую последовательность обменов всегда возможно.

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

В первой строке вводится целое число \(N\) - размер входного массива (1 <= \(N\) <= 100). Вторая строка содержит \(N\) целых чисел - исходную перестановку чисел от 1 до \(N\) в массиве. Изначально ни одно число не стоит на своем месте.

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

Выведите \(K\) строк, где \(K\) - количество обменов в Вашей сортировке. На каждой строке выведите по два числа \(x_i\) и \(y_i\), разделенных пробелом - позиции в массиве, числа на которых следует поменять местами на i-ом обмене. Помните, что должно выполняться условие |\(x_i\) - \(y_i\)| = 1 и что нельзя перемещать число, которое уже стоит на своем месте.

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

В приведенном примере массив последовательно имеет следующий вид:
исходный вид массива
2 3 1 6 4 5
поменяли местами числа на 2 и 3 позициях
2 1 3 6 4 5
поменяли местами числа на 1 и 2 позициях
1 2 3 6 4 5
поменяли местами числа на 4 и 5 позициях
1 2 3 4 6 5
поменяли местами числа на 5 и 6 позициях
1 2 3 4 5 6

Примеры
Входные данные
6
2 3 1 6 4 5
Выходные данные
2 3
1 2
4 5
5 6
Страница: 1 Отображать по:
Выбрано
:
Отменить
|
Добавить в контест