мастер-класс_осень_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`

Задача C. Hot-keys ≡

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

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

Условие

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

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

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

Для каждой комбинации позицией считается самое крайнее от начала строки (заголовка элемента) появление символа горячей клавиши. Из всех возможных решений с одинаковым количеством горячих клавиш, ваша программа должна выбрать единственное с минимальной суммой позиций горячих клавиш. Если решений с такой минимальной суммой несколько, то выведите любое из них.

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

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

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

Выходной файл должен содержать N строк с одинаковыми заголовками, как и во входном файле. В каждом заголовке, которому была назначена какая-то комбинации, перед самым левым вхождением символа из горячей клавиши необходимо добавить символ '&' (ASCII 38).

Ограничения

1 ≤ N ≤ 10, все заголовки имеют длину от 1 до 10 символов и состоят из строчных латинских букв.

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

№	Входной файл (`input.txt`)	Выходной файл (`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`