Задача A. Сумма двух чисел

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

Условие

Вывести сумму двух заданных чисел.

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

На первой строке входного файла находятся два целых числа a и b ( − 109 ≤ a, b ≤ 109).

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

Вашей программе требуется вывести единственное число — сумму заданных чисел a + b.

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

Входной файл (input.txt) Выходной файл (output.txt)
1
2 3
5
2
17 -18
-1

Задача AA. Сколько селёдок?

Автор:П. Месенёв, А. Маметьев, Yandex cup   Ограничение времени:2 сек
Входной файл:Стандартный вход   Ограничение памяти:256 Мб
Выходной файл:Стандартный выход  

Условие

Витя, Петя и Олег решили сходить на рыбалку за селёдками. В море селёдок много и каждая из них весит строго целое количество килограмм. Олег провёл классификацию рыбы и выяснил, что массы селёдок образуют последовательность, заданную следующим образом: xi = xi − 1 + i. Минимальный вес селёдки составляет один килограмм. Мальчики взяли с собой ведро, в которое помещается N килограмм рыбы. Разумеется, они хотели бы вернуться домой с полным ведром селёдок.

Так как рыбачить умеет только Витя, а Олег уже свою часть работы закрыл исследованием, то Петя вызвался посчитать, какое минимальное количество селёдок Вите требуется поймать, пока Петя и Олег будут греться у костра.

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

Входной файл содержит единственное число N — вместимость ведра в килограммах.

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

В выходной файл выведите число — минимальное число селёдок.

Ограничения

1 ≤ N ≤ 5 * 1011

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

Стандартный вход Стандартный выход
1
3
1
2
5
3

Задача B. Точка в углу

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

Условие

Прямоугольник со сторонами, параллельными осям координат, задан координатами противоположных вершин (x1, y1) и (x2, y2).

Будем считать, что точка (x, y) внутри прямоугольника находится в углу, если расстояние от точки до одной из вершин прямоугольника строго меньше, чем до центра прямоугольника.

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

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

Входной файл содержит целые числа x1 y1 x2 y2 x y — координаты вершин прямоугольника и точки.

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

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

Ограничения

 − 104 ≤ x1,y1,x2,y2 ≤ 104

min(x1, x2) ≤ x ≤ max(x1, x2)

min(y1, y2) ≤ y ≤ max(y1, y2)

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

Входной файл (input.txt) Выходной файл (output.txt)
1
100 200 300 400 290 210
CORNER
2
100 200 300 400 200 300
CENTER

Задача C. Сумма элементов последовательности

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

Условие

Последовательность bi получается из последовательности ai по следующему закону: bi = ( − 1)ai.

Требуется написать программу, вычисляющую сумму N элементов последовательности bi.

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

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

Далее следует N чисел, задающих последовательность ai.

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

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

Ограничения

1 ≤ N ≤ 106

0 ≤ |ai| ≤ 109

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

Входной файл (input.txt) Выходной файл (output.txt)
1
4
1 7 12 13
-2
2
6
-1 -2 -3 -4 -5 -6
0

Задача D. Массив наоборот

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

Условие

Во входном файле дан массив целых чисел a1, a2, ..., aN. Требуется вывести этот массив в обратном порядке.

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

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

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

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

Ограничения

1 ≤ N ≤ 100000

 − 109 ≤ ai ≤ 109

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

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

Задача E. Вид из окна

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

Условие

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

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

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

Входные данные содержат целые число n — количество мест в электричке. Далее следует n целых чисел ai — уровень загрязнения i-го окна. Окна нумеруются с единицы.

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

Ответ — одно целое число.

Ограничения

5 ≤ n ≤ 10000

1 ≤ ai ≤ 10000

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

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

Задача F. Максимальный перепад

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

Условие

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

Карта региона представляет собой матрицу размером N x N клеток, в каждой клетке которой содержится средняя высота определённого района над уровнем моря. Максимальным перепадом высот называется максимальная величина, на которую отличаются средние высоты двух районов, соседних на карте по горизонтали или по вертикали. Требуется по карте региона определить максимальный перепад высот в нем.

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

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

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

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

Ограничения

1 ≤ N ≤ 100. Все высоты — целые числа от 0 до 231−1

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

Входной файл (input.txt) Выходной файл (output.txt)
1
3
1 1 1
1 2 1
1 2 3
2

Задача G. План эвакуации

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

Условие

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

Коридор является одномерным и состоит из N клеток, в каждой клетке может находиться только один человек

План эвакуации представляет из себя строку из N символов 'L', 'R', 'X'. Символ 'L' означает, что человек, находящийся в данной клетке, в случае эвакуации должен пойти в соседнюю клетку слева. Аналогично, символ 'R' означает, что следует пойти вправо. Символ 'X' означает, что в этой клетке расположен выход.

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

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

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

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

Первая строка входного файла содержит числа N, M и K — размер описания плана эвакуации, количество выходов и ограничение на каждый выход.

Вторая строка входного файла содержит M целых чисел xi — координаты выходов. Координаты заданы в порядке возрастания.

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

В выходной файл выведите единственную строку — описание плана эвакуации, удовлетворяющего всем вышеописанным условиям, или строку NO, если такого плана не существует.

Ограничения

1 ≤ M ≤ N ≤ 105

1 ≤ K ≤ 105

1 ≤ xi ≤ N

Описание подзадач и системы оценивания

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

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

По запросу сообщается результат окончательной проверки на каждом тесте.

Подзадача Баллы Дополнительные ограничения Необходимые подзадачи
N, K
1 25 1 ≤ N ≤ 102
2 20 1 ≤ N ≤ 105, K = N
3 20 1 ≤ N ≤ 104 1
4 35 1 ≤ N ≤ 105 1-3

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

Входной файл (input.txt) Выходной файл (output.txt)
1
6 1 7
5
RRRRXL
2
10 1 5
5
NO

Задача H. Максимальный элемент массива

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

Условие

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

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

В первой строке записано одно целое число N — количество элементов в массиве.

Далее следует N целых чисел ai — элементы массива.

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

Выведите единственное целое число — наибольший элемент массива.

Ограничения

1 ≤ N ≤ 103

 − 106 ≤ ai ≤ 106

Описание подзадач и системы оценивания

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

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

По запросу сообщается результат окончательной проверки на каждом тесте.

Подзадача Баллы Дополнительные ограничения Необходимые подзадачи
ai
1451 ≤ ai ≤ 106
255 − 106 ≤ ai ≤ 1061

Подсказка

Для того чтобы считывать элементы массива на языке Pascal следует использовать функцию read(). Применение функции readln() невозможно, так как все элементы массива записаны в одной строке.

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

Стандартный вход Стандартный выход
1
3
1 3 2
3
2
5
8 5 6 10 3
10
3
1
1000000
1000000

Задача I. Факториал

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

Условие

Для заданного натурального числа N выведите значение N!

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

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

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

Выходной файл должен содержать единственное целое число N!

Ограничения

0 ≤ N ≤ 12.

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

Входной файл (input.txt) Выходной файл (output.txt)
1
3
6

Задача J. Фибоначчи_rec

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

Условие

Необходимо вывести N первых чисел Фибоначчи, начиная с 0.

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

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

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

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

Ограничения

Unbalanced TeX0 ≤ N ≤ 10

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

Входной файл (input.txt) Выходной файл (output.txt)
1
2
0 1

Задача J. Код Хаффмана

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

Условие

Построить код Хаффмана для алфавита из N символов и соответствующих им частот встречаемости.

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

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

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

Выходной файл должен содержать N строк вида hi — коды Хаффмана для символов в порядке, соответствующем входному файлу. Каждый код должен представлять собой строку из цифр 0 и 1. Если существует несколько решений, вывести любое из них.

Ограничения

2 ≤ N ≤ 100, 0 ≤ fi ≤ 100000.

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

Входной файл (input.txt) Выходной файл (output.txt)
1
6
45
13
12
16
9
5
0
101
100
111
1101
1100

Задача K. Два компьютера

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

Условие

Имеется два компьютера с одинаковой производительностью и N программ, которые необходимо выполнить. Известно, что i-я программа требует для выполнения на любом из компьютеров Ti секунд. Программы можно выполнять в любом порядке, но прерывать однажды запущенную программу нельзя. Сразу после окончания одной программы можно запускать следующую.

Требуется распределить программы между компьютерами таким образом, чтобы время на их выполнение оказалось наименьшим. Например, программы длительностью 7, 10, 3, 5, 6 можно выполнить за 16 секунд, если на первом компьютере выполнять вторую и четвертую программу, а на втором — остальные три.

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

Входной файл содержит число N, за которым следуют числа T1 … TN. Все числа — целые, разделены пробелами.

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

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

Ограничения

1 ≤ N ≤ 20, 1 ≤ Ti ≤ 1000

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

Входной файл (input.txt) Выходной файл (output.txt)
1
5 7 10 3 5 6
16

Задача L. Короткий текст и немного слов

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

Условие

Имеется текст и N слов. Длина текста L символов, длина каждого слова — от 1 до 255 символов. Требуется для каждого слова определить, входит ли оно в текст. Все слова и текст состоят из латинских букв. Заглавные и строчные буквы считаются различными.

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

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

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

Выходной файле должен содержать N чисел 1 или 0, обозначающих, что соответствующее слово входит или не входит в текст.

Ограничения

1 ≤ L ≤ 255, 1 ≤ N ≤ 1000.

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

Входной файл (input.txt) Выходной файл (output.txt)
1
Longlongstring
2
short
string
0 1

Задача M. Укорачивание текста

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

Условие

По заданному тексту длины N и образцу длины K определить длину минимальной подстроки в тексте, которая удовлетворяет данному образцу. Текст состоит только из маленьких латинских букв. Образец содержит маленькие латинские буквы и символ '*', заменяющий любое множество любых символов(в том числе пустое).

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

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

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

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

Ограничения

1 ≤ N ≤ 1000000, 1 ≤ K ≤ 100

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

Входной файл (input.txt) Выходной файл (output.txt)
1
3 4
a*b
abab
2

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

Автор:А. Кленин   Ограничение времени: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

Задача O. Усовершенствованный шифр Цезаря

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

Условие

Требуется написать программу для преобразования строки S в строку H в соответствии с правилом: символ строки H с номером i равен соответствующему символу строки S, смещённому на i символов по алфавиту (символы в строке нумеруются с 1; символ 'Z', смещённый на 1 символ, равен символу 'A').

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

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

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

Выходной файл должен содержать строку H — закодированное сообщение.

Ограничения

Строка во входном файле содержит от 1 до 255 символов.

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

Входной файл (input.txt) Выходной файл (output.txt)
1
AAAAAAAAAAAAAAAAAAAAAAAAAAAA
BCDEFGHIJKLMNOPQRSTUVWXYZABC
2
QWERTY
RYHVYE

Задача P. Количество битов в числе

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

Условие

Дано целое неотрицательное число x, требуется посчитать количество не нулевых битов в числе.

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

Первая строка входного файла содержит число x.

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

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

Ограничения

0 ≤ x ≤ 2 ⋅ 109

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

Входной файл (input.txt) Выходной файл (output.txt)
1
1
1
2
15
4

Задача Q. K-й бит в числе

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

Условие

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

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

Первая строка входного файла содержит два числа x, k.

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

Входной файл должен содержать одно число  — значение k-го бита числа x.

Ограничения

0 ≤ x ≤ 2 ⋅ 109

0 ≤ k ≤ 300

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

Входной файл (input.txt) Выходной файл (output.txt)
1
0 10
0
2
123 0
1
3
12345 100
0

Задача R. Единственный канал у пикселя

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

Условие

Витя, Петя и Олег — программисты. Они решили написать свой графический редактор на библиотеке Qt!

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

Петя и Олег знают, что цвет пикселя обычно кодируется тремя значениями — red, green, blue. Каждый в диапазоне от 0 до 255. Но модуль Вити возвращает цвет пикселя в виде единственного числа. В битах с 0 по 7 включительно отражена интенсивность синего канала. С 8 по 15 зелёного, а с 16 по 23 интенсивность красного.

Разработчикам нужно не много — оставить только один цветовой канал и вернуть полученный цвет в том же формате. К сожалению, Петя и Олег проспали лекцию по битовому представлению чисел в памяти компьютера, и теперь им нужна ваша помощь.

На вход подаётся число, и буква r\g\b — канал, который нужно оставить. Ваша задача получить итоговый цвет в том же формате.

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

Входные данные содержат число n и символ m — значение цвета и необходимый канал.

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

Выходные данные должны содержать единственное число — цвет в числовом представлении.

Ограничения

0 ≤ n ≤ 16777215

m ∈ {′r′, ′g′, ′b′}

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

Стандартный вход Стандартный выход
1
6579300 g
25600

Задача S. Битовый диктатор

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

Условие

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

Возьми число a, подели нацело его на 4 (22), далее умножь на 16 (24), после этого сделай побитовое "ИСКЛЮЧАЮЩЕ ИЛИ" с числом b, получившийся результат умножь на 2 (21), и сделай побитовое "ИЛИ" с числом c. Ответом будет побитовое "И" уже получившегося результата и числа 1073741823.

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

Первая строка входного файла содержит три числа a, b и c.

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

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

Ограничения

0 ≤ a, b, c ≤ 2 ⋅ 105

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

Входной файл (input.txt) Выходной файл (output.txt)
1
0 10 25
29
2
123 123 123
895

Задача T. Сеть Фейстеля

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

Условие

Необходимо реализовать шифрование Сетью Фейстеля

Псевдокод шифрования:

    
      for i in range(blocks):
          for r in range(rounds):
              TEMP = L[i]
              L[i] = R[i]
              R[i] = TEMP XOR F(K[r], R[i])
      
  

L[i] - первая половина i-го блока

R[i] - вторая половина i-го блока

K[r] - ключ шифрования на r-ом раунде, в данной задаче размер ключа равен размеру половины блока

F - функция шифрования, в данной задаче используется XOR

В случае если длина строки не кратна размеру блока, строка дополняется символами '\0'

Половины блока имеют одинаковую длину

Длина блока всегда четная

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

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

Первая строка теста: 2 целых числа - количество раундов, размер блока в байтах

Вторая строка теста: раундовые ключи шифрования одной HEX строкой

Третья строка теста: целевая ASCII строка, которую необходимо зашифровать

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

Выходной файл должен содержать N строк - шифротекстов HEX-ом для каждой целевой строки

Ограничения

Длина строки <= 65536

Размер блока <= 64

Кол-во раундов <= 32

Кол-во тестов <= 335

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

Входной файл (input.txt) Выходной файл (output.txt)
1
1
2 4
90A314CE
Phad1d2Ref
A1AFD4059395B509F5C5E10B

Задача U. Честная очередь

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

Условие

В одном из травмпунктов города Владивостока прием пациентов осуществляется по следующим правилам:

Обычно во все кабинеты имеется очередь. Некоторые люди, если им надо попасть сразу в два кабинета, занимают две очереди, а остальные — сначала проходят рентген, а потом занимают очередь в кабинет вторичного приема.

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

По заданной последовательности появления пациентов выясните время, которое понадобится каждому из пациентов, чтобы посетить все назначенные ему кабинеты. При этом следует считать, что для любого пациента длительность приема в кабинете рентгенографии равна P минут, длительность приема в кабинете второго осмотра равна Q минут, а время первичного приёма равно нулю.

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

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

В каждом наборе первое число означает время прихода пациента ti, измеренное в минутах с начала приема. Далее идет число, обозначающее, в какие кабинеты требуется попасть i-му пациенту — 1, если сперва в кабинет рентгенографии и 2, если сразу в кабинет вторичного приема.

Для пациентов, которым требуется сделать снимок, далее идет число 1 или 2, обозначающее, займет ли пациент он место в одной очереди или в двух.

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

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

Ограничения

1 ≤ N ≤ 100, 1 ≤ P, Q ≤ 15, 0 ≤ ti ≤ 1000, ti < ti + 1

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

Входной файл (input.txt) Выходной файл (output.txt)
1
2 5 10
0 1 1
5 1 1
15 20
2
2 5 5
0 1 1
5 2  
15 5
3
3 5 10 0 1 2 2 2 3 2
32 10 19

Задача V. Заколдованный аквариум

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

Условие

По мотивам романа А. и Б. Стругацких “Понедельник начинается в субботу”.

Очередной понедельник выдался в НИИЧАВО (Научно-Исследовательский Институт ЧАродейства и ВОлшебства) на удивление беспокойным. Началось все с проблем в отделе исследования живой, мёртвой и водопроводной воды, куда на прошлой неделе завезли новый аквариум. Туда и вошел Привалов в самый интересный момент беседы между Амвросием Амбруазовичем Выбегалло и заведующим отделом смысла жизни Кристобалем Хозевичем Хунтой. Сейчас Кристобаль Хозевич в красках описывал, какие могут возникнуть повреждения всей новейшей системы безопасности, недавно установленной в институте, от всего того количества воды, которым сейчас затапливался его отдел.

 — Подождите, остановил его речь Выбегалло, вот закончим проверку и выключим воду.

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

 — Нет, это категорически невозможно! — Возражал Выбегалло, — как вы себе это представляете? Мы проводим важнейший эксперимент!

 — Может быть, объясните, что здесь все-таки происходит? - вмешался в разговор Привалов

 — Позвольте, я объясню, начал было Выбегалло, но Кристобаль Хозевич не дал ему закончить, и, сделав руками несколько пассов, произнес, — вот теперь порядок, ничего не вливается и не выливается, можете объяснять.

 — Ну, раз вы все-таки запечатали отверстия, то спешки особой нет, — продолжил Амвросий Амбруазович, — на прошлой неделе мне, доставили новый большой аквариум, необычной конструкции, а если быть точным, с несколькими прямоугольными отверстиями на лицевой стороне, вот посмотрите.

Привалов, наконец, осмотрел новый аквариум. Он представлял собой прямоугольный параллелепипед размерами W × H × L метров без верхней крышки, на лицевой стороне которого было вырезано N квадратных отверстий c длиной стороны ai метров. Сверху над аквариумом висела большая труба, через которую в него поступало M кубических метров воды в секунду.

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

 — А более сухого способа вы не нашли, — вставил свою реплику Хунта

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

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

Через несколько минут он передал Привалову формулу расчета потока воды из отверстий в аквариуме. Поскольку аквариум до эксперимента был специально заколдован, формула была оказалась простой: через отверстие площадью b квадратных метров в одну секунду будет вытекать V × b кубических метров воды.

В начале эксперимента аквариум пуст. Через некоторое время после того, как из трубы начнёт поступать вода, уровень в воды в аквариуме стабилизируется (либо аквариум переполнится). Теперь осталось только написать программу, определяющую высоту стабильного уровня воды.

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

Входной файл содержит числа V M N — соответственно скорость вытекания воды (в м / с), поток втекающей воды (м3 / c) и количество отверстий в лицевой стороне аквариума. Далее следует N троек чисел xi yi ai — координаты нижнего левого угла и длина стороны. отверстия номер i. Отверстия не пересекаются и не соприкасаются друг с другом.

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

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

Ограничения

0 < V, M ≤ 1000, 0 ≤ N ≤ 100, 0 ≤ xi, yi, ai ≤ 106.

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

Входной файл (input.txt) Выходной файл (output.txt)
1
1 4 3
1.0 1.0 4.0
6.0 2.0 4.0
11 5.0 3.0
2.0

Задача W. Дипломы

Автор:Центральная предметно-методическая комиссия по информатике   Ограничение времени:2 сек
Входной файл:diploma.in   Ограничение памяти:64 Мб
Выходной файл:diploma.out  

Условие

Когда Петя учился в школе, он часто участвовал в олимпиадах по информатике, математике и физике. Так как он был достаточно способным мальчиком и усердно учился, то на многих из этих олимпиад он получал дипломы. К окончанию школы у него накопилось N дипломов, причем, как оказалось, все они имели одинаковые размеры: W — в ширину и H — в высоту.

Сейчас Петя учится в одном из лучших российских университетов и живет в общежитии со своими одногруппниками. Он решил украсить свою комнату, повесив на одну из стен свои дипломы за школьные олимпиады. Так как к бетонной стене прикрепить дипломы достаточно трудно, то он решил купить специальную доску из пробкового дерева, чтобы прикрепить ее к стене, а к ней — дипломы. Для того чтобы эта конструкция выглядела более красиво, Петя хочет, чтобы доска была квадратной и занимала как можно меньше места на стене. Каждый диплом должен быть размещен строго в прямоугольнике размером W на H. Прямоугольники, соответствующие различным дипломам, не должны иметь общих внутренних точек.

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

Система оценивания

Решения, правильно работающие только при W, H, N ≤ 1000, будут оцениваться в 40 баллов.

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

Входной файл содержит три целых числа: W, H, N

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

В выходной файл необходимо вывести ответ на поставленную задачу.

Ограничения

1 ≤ W, H, N ≤ 109

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

Входной файл (diploma.in) Выходной файл (diploma.out)
1
2 3 10
9

Problem X. Square sort

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 &le; N &le; 3000. Sequence elements are less than 109 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

Problem Y. Lin-log sort

Author:StdAlg   Time limit:1 sec
Input file:input.txt   Memory limit:64 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 &le; N &le; 100000. Sequence elements are less than 109 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

Задача Z. k-я порядковая статистика

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

Условие

K-й порядковой статистикой N-элементного массива называется число Аk, которое будет стоять на K-м месте после сортировки этого массива по возрастанию.

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

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

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

Выходной файл должен содержать K-ю порядковую статистику исходного массива.

Ограничения

1 ≤ N ≤ 106, 1 ≤ K ≤ N,  − 231 ≤ Ai ≤ 231 − 1

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

Входной файл (input.txt) Выходной файл (output.txt)
1
3 2 
2 3 1
2

Задача Z. Финишные позиции

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

Условие

На одном из этапов марсианских гонок по кольцевому треку вышла из строя программа, рассчитывающая финишные позиции гонщиков. На трассе имеется специальное оборудование, формирующее хронику гонки — список машин, пересекающих финишную черту. То есть, когда машина заканчивает очередной круг, пересекая финишную черту, её номер добавляется в список. Например, если список имеет вид 47874874, то это означает, что первый круг закончили машины с номерами 478 в указанном порядке, на втором круге машина 7 обогнала машину 4, а на третий круг закончили только машины 74, а машина 8 либо сломалась, либо всё ещё находится на втором круге.

Требуется написать программу, которая по заданному списку машин определит их финишные позиции.

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

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

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

Далее следуют N чисел, задающие список.

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

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

Ограничения

1 ≤ N ≤ 106

Номера машин являются целыми неотрицательными числами, не превосходящими 109

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

Входной файл (input.txt) Выходной файл (output.txt)
1
3
5 1 10
5 1 10
2
8
4 7 8 7 4 8 7 4
7 4 8
3
16
17 88 39 88 17 39 88 17 88 17 39 39 17 39 17 222222222
17 39 88 222222222

1.455s 0.011s 73