мастер-класс_осень_2012

Problem A. Lin-log sort ≡

problems
details
visible spaces
basic formulae
wide text
editor

Author:	StdAlg	Time limit:	1 sec
Input file:	input.txt	Memory limit:	8 Mb
Output file:	output.txt

Statement

You are to write a program that receives a sequence of integer numbers and sorts it, i. e. writes out all elements in ascending order.

Input file format

Input file contains integer N — length of the sequnece, followed by N integer numbers — elements of the sequence.

Output file format

Output file must contain N integer numbers, which must be elements of the source sequence printed in ascending order.

Constraints

0 ≤ N ≤ 100000. Sequence elements are less than 10⁹ by absolute value.

Sample tests

No.	Input file (`input.txt`)	Output file (`output.txt`)
1	`5 4 3 10 3 1`	`1 3 3 4 10`

Задача B. Наибольшая возрастающая подпоследовательность ≡

задачи
детали
видимые пробелы
простые формулы
широкий текст
редактор

Входной файл:	input.txt		Ограничение времени:	2 сек
Выходной файл:	output.txt		Ограничение памяти:	64 Мб

Условие

Дана последовательность из N целых чисел. Найдите любую из ее наибольших строго возрастающих подпоследовательностей.

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

Во входном файле находится число N, а за ним следует последовательность a_i из N целых чисел.

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

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

Ограничения

1 ≤ N ≤ 100000;  − 10⁹ ≤ a_i ≤ 10⁹

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

№	Входной файл (`input.txt`)	Выходной файл (`output.txt`)
1	`5 123 456 124 124 125`	`3 1 4 5`

Problem C. Hot-keys ≡

problems
details
visible spaces
basic formulae
wide text
editor

Author:	A. Klenin	Time limit:	5 sec
Input file:	input.txt	Memory limit:	64 Mb
Output file:	output.txt

Statement

When designing dialog forms for interactive programs, it is important to assign hot-keys (known also as accelerator keys) to each dialog element, so as to facilitate keyboard input.

For better mnemonics, hot-keys are assigned based on the letters of dialog elements' captions, usually favoring letters near the beginning of caption. Manual hot-keys distribution can be tedious and error-prone, as one must be careful not to assign same letter to different elements.

Your program will be given a list of captions. It must assign unique hot-keys to as many captions of possible. Each assigned hot-key must be a letter from the corresponding caption.

For each hot-key, position is the leftmost occurrence of the hot-key letter in the corresponding caption. From all solutions with the same numbers of hot-keys, your program must choose the one with minimal sum of hot-key positions. If there is still more than one optimal solution, output any of them.

Input file format

Input file contains number of captions N followed by N lines with captions.

Output file format

Output file must contain N lines with the same captions as in input. In those captions which have hot-key assigned, leftmost occurrence of hot-key letter must be preceded with '&' (ASCII 38).

Constraints

1 ≤ N ≤ 10, all captions are from 1 to 10 characters in length and consist of small Latin letters.

Sample tests

No.	Input file (`input.txt`)	Output file (`output.txt`)
1	`3 yes no cancel`	`&yes &no &cancel`
2	`4 abc bca acb aaaa`	`&abc &bca a&cb aaaa`

Задача D. LCA ≡

задачи
детали
видимые пробелы
простые формулы
широкий текст
редактор

Автор:	И. Туфанов	Ограничение времени:	2 сек
Входной файл:	input.txt	Ограничение памяти:	64 Мб
Выходной файл:	output.txt

Условие

Дано дерево из N вешрин, все некоторым образом пронумерованы, а корень имеет номер 1. Найдите LCA для некоторых пар вершин.

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

Первая строка входного файла состоит из единственного числа N. Далее в N − 1 строке следует описание дерева: пары соединенных вершин. После этого до конца файла записаны пары номеров веришин, для которых следует найти LCA. Количество этих пар не превосходит 10^5.

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

В выходном файле для каждого запроса выведите единственное число: номер LCA.

Ограничения

1 ≤ N ≤ 10⁵

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

№	Входной файл (`input.txt`)	Выходной файл (`output.txt`)
1	`6 1 3 2 3 3 4 3 5 6 2 1 2 6 5`	`1 3`

Задача E. Выборы заведующего кафедрой ≡

задачи
детали
видимые пробелы
простые формулы
широкий текст
редактор

Автор:	Г. Гренкин, И. Туфанов	Ограничение времени:	2 сек
Входной файл:	input.txt	Ограничение памяти:	256 Мб
Выходной файл:	output.txt

Условие

В ДВФУ произошло укрупнение кафедры информатики. В связи с этим встал вопрос выборе нового заведующего кафедрой. На кафедре работает много преподавателей и непросто выбрать самого достойного. Посовещавшись, преподаватели занумеровали себя и для преподавателя с номером i определили следующие числа:

m_i — уровень познаний в математике;
p_i — уровень познаний в программировании;
t_i — преподавательское мастерство;

Чем больше число, тем выше уровень мастерства преподавателя в соответствующей области.

Считается, что, i-й преподаватель является кандидатом на должность заведующего кафедрой в том и только том случае, когда для него не найдётся такого j-того преподавателя, что одновременно m_j > m_i, p_j > p_i, t_j > t_i.

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

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

Входной файл содержит натуральное число n — количество преподавателей. Далее следует n троек натуральных чисел m_i p_i t_i.

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

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

Ограничения

1 ≤ n ≤ 10⁵

1 ≤ m_i, p_i, t_i ≤ 10⁹

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

№	Входной файл (`input.txt`)	Выходной файл (`output.txt`)
1	`4 2 3 4 1 1 3 2 1 8 3 2 10`	`1 4`

Задача F. Сбалансированное дерево revisited ≡

задачи
детали
видимые пробелы
простые формулы
широкий текст
редактор

Автор:	A. Klenin	Ограничение времени:	5 сек
Входной файл:	input.txt	Ограничение памяти:	256 Мб
Выходной файл:	output.txt

Условие

Дана последовательность целых чисел. Каждое прочитанное число обрабатывается следующим образом:

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

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

Входной файл содержит последовательность чисел.

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

Выходной файл должен содержать последовательность чисел, отсортированных по возрастанию.

Ограничения

Количество чисел находится в диапазоне от 0 до 10⁶, сами числа — в диапазоне от  − 2³¹ до 2³¹ − 1.

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

№	Входной файл (`input.txt`)	Выходной файл (`output.txt`)
1	`3 2 1 3 0`	`1 2 3`
2	`5 -1 6 -5 5 0`	`5 6`