Задача A. groupby group

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

Условие

Необходимо написать программу, которая группирует студентов по их группам.

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

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

Группа и имя студента разделены символом табуляции.

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

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

Сами группы следуют также в алфавитном порядке.

Ограничения

1 ≤ n ≤ 105

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

Входной файл (input.txt) Выходной файл (output.txt)
1
3
M8103	Sidorov Sidor
M8888	Petrov Petr
M8103	Ivanov Ivan
M8103
Ivanov Ivan
Sidorov Sidor
M8888
Petrov Petr

Задача B. Длинная прогрессия

Автор:Приморская краевая олимпиада школьников по программированию 1998/1999   Ограничение времени:1 сек
Входной файл:input.txt   Ограничение памяти:64 Мб
Выходной файл:output.txt  

Условие

Задана последовательность состоящая из N натуральных чисел Ai. Необходимо определить, можно ли, переставляя элементы этой последовательности, выстроить их в отрезок неубывающей арифметической прогрессии.

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

В первой строке входного файла содержится число N

Во второй строчке входного файла содержатся N чисел, задающие входную последовательность

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

В выходном файле должно содержаться:

Ограничения

2 ≤ N ≤ 105

0 ≤ |Ai| ≤ 106

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

Входной файл (input.txt) Выходной файл (output.txt)
1
9
80 50 10 30 70 40 20 60 90
10 10

Задача C. Будь как все

Входной файл:Стандартный вход   Ограничение времени:1 сек
Выходной файл:Стандартный выход   Ограничение памяти:512 Мб

Условие

Дан массив чисел. Нужно заменить в нем максимальный элемент на минимальный из этого же массива. Если максимальных несколько — заменить каждый из них.

Формат входных данных

Входные данные содержат несколько чисел, разделенных пробелами.

Формат выходных данных

Выходные данные должны содержать массив, в котором максимальные элементы заменены на минимальный. Элементы массива должны быть разделены пробелами.

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

Стандартный вход Стандартный выход
1
3 -1 2 4 9 6
3 -1 2 4 -1 6
2
5 4 1 5 2
1 4 1 1 2

Задача D. Библиотекарь

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

Условие

Аполлинарий Матвеевич — старый, седой библиотекарь. Сегодня он в очень хорошем настроении, потому что библиотеке подарили компьютер.

Помощники Аполлинария Матвеевича составили базу данных книг библиотеки. Все книги, хранящиеся в библиотеке, разбиты по областям знаний, и в каждой книге затронут ряд тем. При этом и каждая тема, и каждая книга могут принадлежать только одной области знаний. В базе данных хранится список областей знаний и содержится информация о книгах, относящихся к каждой области знаний. Кроме того, для каждой книги составлен список тем, затронутых в ней.

Однажды в библиотеку зашёл читатель. Он дал Аполлинарию Матвеевичу список тем и попросил его подобрать книги по этим темам. Аполлинарий Матвеевич обрадовался: у него есть база данных! Но стоп: как найти в базе данных нужную информацию? Для этого нужна программа.

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

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

Первая строка входного файла содержит целое число N — количество областей знаний.

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

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

Далее входной файл содержит целое число M — количество тем в списке, подготовленном читателем. Далее следует список тем.

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

Для каждой темы требуется вывести строку "Topic: название темы". Далее должна следовать строка "Subject: название области знаний". Далее должна следовать строка "Books:" (без пробелов). Далее должен следовать список книг в том порядке, в котором они перечислены во входном файле.

Ограничения

1 ≤ N ≤ 50

1 ≤ M ≤ 10

Количество книг, относящихся к определённой области знаний, от 1 до 100.

Количество тем, затронутых в определённой книге, от 1 до 10.

Все названия во входном файле имеют длину от 1 до 50 символов и состоят из маленьких латинских букв.

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

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

Входной файл (input.txt) Выходной файл (output.txt)
1
2
mathematics
2
algebra
3
lines
equations
coordinates
geometry
3
triangles
coordinates
lines
physics
2
mechanics
3
force
velocity
mass
gravitation
2
force
mass
5
force
triangles
velocity
coordinates
mass
Topic: force
Subject: physics
Books:
mechanics
gravitation
Topic: triangles
Subject: mathematics
Books:
geometry
Topic: velocity
Subject: physics
Books:
mechanics
Topic: coordinates
Subject: mathematics
Books:
algebra
geometry
Topic: mass
Subject: physics
Books:
mechanics
gravitation

Задача E. Ежеминутные автобусы

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

Условие

На автобусную остановку каждую минуту подходит автобус одного из маршрутов. Диспетчерская служба собрала данные за N минут — номера маршрутов каждого автобуса.

Требуется определить максимально возможное время ожидания для пассажира, желающего уехать определённым маршрутом. Т.е. в данной последовательности номеров маршрутов нужно найти два самых удаленных числа, равных между собой. Например, для последовательности 2, 11, 2, 2, 25, 11, 25, 11 максимальное время ожидания равно 4 — для маршрута номер 11.

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

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

Все числа целые. Каждый номер маршрута встречается не менее двух раз.

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

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

Ограничения

2 ≤ i ≤ 106

1 ≤ ai ≤ 100

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

Входной файл (input.txt) Выходной файл (output.txt)
1
8
2 11 2 2 25 11 25 11
4
2
4
23 23 41 41
1

Задача F. Дифтонги

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

Условие

Слова марсианского языка состоят из малых латинских букв. Буквы a, e, i, o, u, y считаются гласными, остальные — согласными.

Дифтонгом называется пара подряд идущих гласных букв, окружённых либо согласными буквами, либо границами слова. Например, в слове preemptio имеется два дифтонга, а в слове aaa — ни одного.

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

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

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

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

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

Ограничения

1 ≤ N ≤ 100

Слова содержат от 1 до 255 символов.

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

Входной файл (input.txt) Выходной файл (output.txt)
1
3
e
ee
eee
ee
2
3
aabbee
cyydyyy
xiixiixiii
aabbee
xiixiixiii

Problem G. Elementary arithmetic

Author:A. Zhuplev, A. Klenin   Time limit:1 sec
Input file:input.txt   Memory limit:256 Mb
Output file:output.txt  

Statement

Underwater arithmetic is very elementary. There are just two operations: WITH and WITHOUT which mean addition and subtraction respectively.

Underwater mathematicians did not yet invent brackets, so all expressions are calculated from right to left. For example, the expression 3 WITH 5 WITHOUT 4 WITHOUT 7 is calculated as (3 + (5 − (4 − 7))).

Scientists of Nearsea Institute of Underwater Arithmetic need a program to evaluate such expressions.

Input file format

First line of input file contains a single integer N. Following 2 × N + 1 lines describe the expression. Odd lines contain integer operands, even lines contain operations.

Output file format

Output file must contain a single integer — calculation result.

Constraints

1 ≤ N ≤ 103

All operands are in range from 0 to 103.

Sample tests

No. Input file (input.txt) Output file (output.txt)
1
1
2
WITH
3
5
2
3
10
WITHOUT
5
WITH
3
WITH
15
-13

Задача H. Три самые популярные книги

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

Условие

Интернет-магазин сохраняет индивидуальный номер каждой проданной книги, по результатам продаж за последний месяц нужно опубликовать обложки трёх самых популярных книг на главной странице сайта. Вам требуется написать программу, которая по номерам проданных книг определит среди них три самые популярные книги.

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

Входной файл содержит целое число N, за которым следуют N целых чисел B1 B2… BN — номера проданных книг. Среди этих номеров найдутся хотя бы три различных.

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

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

Ограничения

3 ≤ N ≤ 10000, 1 ≤ Bi ≤ 10000

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

Входной файл (input.txt) Выходной файл (output.txt)
1
3 123 456 789
123 456 789
2
6 6 7 7 8 8 8
8 7 6
3
10 13 15 12 18 10 13 19 12 12 19
12 13 19

0.409s 0.009s 27