Задача A. Сложение чисел

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

Условие

Даны два целых числа A и B. Вычислить их сумму A + B.

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

Во входном файле содержатся числа A B, разделённые пробелами.

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

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

Ограничения

 − 10000 ≤ A, B ≤ 10000

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

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

Задача B. Студенты

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

Условие

В университете 3 группы студентов. В каждой группе должно быть не более 30 студентов. Однако, некоторые группы могут быть переполнены, а в некоторых может быть недобор. Необходимо вычислить, сколько останется «лишних» студентов после распределения студентов из переполненных групп в группы с недобором.

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

Входной файл содержит три целых числа (A, B, C) - количество студентов в каждой из трех групп.

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

Выходной файл должен содержать одно целое число - количество "лишних" студентов.

Ограничения

0 ≤ A, B, C ≤ 1000000

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

Входной файл (input.txt) Выходной файл (output.txt)
1
40 25 30
5

Задача C. Кафель в ванной

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

Условие

Требуется написать программу для определения минимального количества плит кафеля, которое потребуется для укладки стены в ванной. Стена имеет длину W и высоту H. Кафельная плита имеет форму квадрата со стороной A. Плитку можно разрезать на любое число частей частей и класть разные её куски в разных частях комнаты.

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

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

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

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

Ограничения

1 ≤ W, H, A ≤ 10000

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

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

Задача E. Кролик

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

Условие

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

Известно, что в начале дня масса кролика равна M кг. На завтрак кролик ест A морковок, на обед — B яблок, а на ужин — C бананов.

Съев морковку, яблоко или банан, кролик увеличит свою массу на 2, 3 или 4 кг соответственно.

Так как морковки — более привычная для кроликов еда, чем яблоки, а яблоки — более привычная еда, чем бананы, съеденная масса яблок не должна превышать съеденную массу морковок, а съеденная масса бананов не должна превышать съеденную массу яблок.

Если вышеуказанное условие не выполняется, кролику станет очень плохо и посетители зоопарка будут недовольны.

Если кролик чувствует себя хорошо, то в конце дня его взвешивают на специальных весах для больших кроликов. Это довольно дорогостоящее оборудование, поэтому сотрудники зоопарка просят вас написать программу, которая выводит массу кролика в конце дня в зависимости от его начальной массы и количества съеденных морковок, яблок и бананов.

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

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

Входной файл содержит 4 целых числа: M, A, B и C.

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

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

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

Ограничения

1 ≤ M, A, B, C ≤ 106

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

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

Problem F. Second Best

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

Statement

Given the sequence of integers A1, A2, …, AN, find a number As such that there exists exactly one Am > As, and for all k ≠ m Ak ≤ As.

Input file format

Input contains N followed by A1 A2… AN.

Output file format

Output should contain a single integer — As, or  − 1 if no such number exists.

Constraints

1 ≤ N ≤ 1000000, 0 ≤ Ai ≤ 109,

Sample tests

No. Input file (input.txt) Output file (output.txt)
1
3
1 2 3
2
2
4
3 3 2 3
-1

Задача G. Шифр Юлия Цезаря

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

Условие

Дана строка, состоящая из маленьких букв латинского алфавита. Требуется закодировать строку при помощи шифра Юлия Цезаря. Суть этого шифра такова: каждая буква сдвигается на три позиции по алфавиту, т.е. a заменяется на d, b — на e, p — на s, w — на z, x — на a, y — на b, z — на c.

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

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

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

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

Ограничения

Длина строки от 1 до 202 символов.

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

Входной файл (input.txt) Выходной файл (output.txt)
1
hello
khoor
2
z
c

Задача H. Ладья на шахматной доске

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

Условие

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

Имеется шахматная доска N на N клеток. В клетке с координатами (X; Y) находится ладья. Требуется вывести шахматную доску с изображением ладьи и всех клеток, в которые она может походить.

Клетки чёрного цвета обозначаются символом '#' (ASCII 35), клетки белого цвета обозначаются символом '.' (точка, ASCII 46), клетка с ладьёй обозначается символом 'X' (ASCII 88), клетка, в которую может походить ладья обозначается символом '*' (ASCII 42).

Ось ординат (OY) направлена вертикально вниз. Верхний левый угол доски имеет чёрный цвет и координаты (1; 1).

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

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

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

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

Ограничения

2 ≤ N ≤ 100

1 ≤ X, Y ≤ N

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

Входной файл (input.txt) Выходной файл (output.txt)
1
8
3 5
#.*.#.#.
.#*#.#.#
#.*.#.#.
.#*#.#.#
**X*****
.#*#.#.#
#.*.#.#.
.#*#.#.#
2
3 1 2
*.#
X**
*.#

Задача I. Симметричная последовательность

Автор:Московская олимпиада для 7-9 кл., 2005   Ограничение времени:3 сек
Входной файл:b.in   Ограничение памяти:64 Мб
Выходной файл:b.out  

Условие

Последовательность чисел назовем симметричной, если она одинаково читается как слева направо, так и справа налево. Например, следующие последовательности являются симметричными:

1 2 3 4 5 4 3 2 1
1 2 1 2 2 1 2 1
Вашей программе будет дана последовательность чисел. Требуется определить, какое минимальное количество и каких чисел надо приписать в конец этой последовательности, чтобы она стала симметричной.

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

Во входном файле записано сначала число N — количество элементов исходной последовательности. Далее записано N чисел — элементы этой последовательности. Элементы последовательности — натуральные числа от 1 до 9.

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

В выходной файл выведите сначала число M — минимальное количество элементов, которое надо дописать к последовательности, а потом M чисел (каждое - от 1 до 9) — числа, которые надо дописать к последовательности.

Ограничения

1 ≤ N ≤ 100

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

Входной файл (b.in) Выходной файл (b.out)
1
9
1 2 3 4 5 4 3 2 1
0
2
5
1 2 1 2 2
3
1 2 1
3
5
1 2 3 4 5
4
4 3 2 1

Задача J. Износ клавиатуры

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

Условие

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

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

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

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

Первая строка входного файла содержит целое число n — количество клавиш на клавиатуре. Вторая строка содержит n целых чисел — c1, c2, …, cn, где ci — количество нажатий, выдерживаемых i-ой клавишей. Третья строка содержит целое число k — общее количество нажатий клавиш, и последняя строка содержит k целых чисел pj (1 ≤ pj ≤ n) — последовательность номеров нажатых клавиш.

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

В выходной файл необходимо вывести n строк, содержащих информацию об исправности клавиш. Если i-ая клавиша сломалась, то i-ая строка должна содержать слово "yes" (без кавычек), если же клавиша работоспособна - слово "no".

Ограничения

1 ≤ n ≤ 105

1 ≤ k, ci ≤ 105

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

Входной файл (input.txt) Выходной файл (output.txt)
1
5
1 50 3 4 3
16
1 2 3 4 5 1 3 3 4 5 5 5 5 5 4 5
yes
no
no
no
yes

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

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

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

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

Задача M. Обход матрицы: спиральный обход

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

Условие

По данному числу N требуется заполнить квадратную матрицу размером NxN целыми числами от 1 до N2; следующим образом:

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

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

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

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

Ограничения

1 <= N <= 100

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

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

Задача N. Пицца

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

Условие

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

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

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

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

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

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

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

Далее следует N различных целых чисел ai — размеры кусочков пиццы, перечисленные в порядке обхода по кругу.

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

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

Ограничения

1 ≤ N ≤ 105

1 ≤ ai ≤ 109

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

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

Подзадача Баллы Дополнительные ограничения Необходимые подзадачи
n
1211 ≤ n ≤ 3
2311 ≤ n ≤ 1031
3481 ≤ n ≤ 1051, 2

Получение информации о результатах окончательной проверки

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

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

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

Задача O. Мы делили...

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

Условие

На день рождения пришли N гостей. Праздничный торт разделили между всеми гостями поровну. После этого неожиданно явились ещё K гостей.

Было решено переделить торт поровну на всех пришедших гостей. Насколько уменьшится доля каждого из гостей, пришедших вовремя?

Ответ вывести в виде несократимой обыкновенной дроби A / B.

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

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

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

Выходной файл должен содержать два целых числа — A B, обозначающие числитель и знаменатель соответственно.

Ограничения

1 ≤ N, K ≤ 104

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

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

Задача P. Простая арифметика

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

Условие

Вам нужно вычислить результат арифметического выражения.

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

Входной файл содержит в единственной строке арифметическое выражение, состоящее из чисел в десятичной системе счисления, знаков  +  (ASCII 4310) и  −  (ASCII 4510). Выражение заканчивается знаком  =  (ASCII 6110).

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

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

Ограничения

Длина входной строки не превосходит 106 символов. Гарантируется, что результат выражения и промежуточных вычислений помещается в знаковый 64-битный тип.

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

Входной файл (input.txt) Выходной файл (output.txt)
1
1+2+3=
6
2
+100-200+300=
200

Задача Q. Арифметика посложнее

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

Условие

Вам нужно вычислить результат арифметического выражения.

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

Входной файл содержит в единственной строке арифметическое выражение, состоящее из чисел в десятичной системе счисления ai, знаков  *  (ASCII 4210) и  /  (ASCII 4710). Выражение заканчивается знаком  =  (ASCII 6110).

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

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

Ограничения

Длина входной строки не превосходит 106 символов. Гарантируется, что результат выражения — целое число, помещающееся в беззнаковый 64-битный тип. 1 ≤ ai ≤ 105

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

Входной файл (input.txt) Выходной файл (output.txt)
1
6*2/3=
4
2
1/4/2*8=
8

Задача R. НОД и числа Фибоначчи

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

Условие

k-тым числом Фибоначчи называется k-тый член последовательности Fk = Fk − 1 + Fk − 2 , F0 = 0 , F1 = 1

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

Во входном файле находятся два числа n и k

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

В выходном файле должно содержаться единственное число — наибольший общий делитель Fn и Fk.

Ограничения

1 ≤ n, k ≤ 100

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

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

Задача S. Тонкий и толстый

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

Условие

На финал чемпионата мира по программированию отправилось так много болельщиков (P человек), что для них пришлось организовать чартерные рейсы. Авиакомпания, доставляющая болельщиков, имеет в своем распоряжении N самолетов. По политическим соображениям, авиакомпания должна использовать для доставки пассажиров все имеющиеся самолёты.

Каждый самолет имеет две модификации. В модификации "Тонкий" самолет может поднять любое количество пассажиров в отрезке [a1, b1]. Перевозить меньше a1 пассажиров экономически невыгодно, а больше b1 пассажиров самолет просто не сможет поднять. В модификации "Толстый" самолет может поднять любое количество пассажиров в отрезке [a2, b2].

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

Рекомендуется рассмотреть частичные решения

N ≤ 1000

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

Во входном файле находятся целые числа N P a1 b1 a2 b2.

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

Если требуемая рассадка пассажиров существует, выведите два целых неотрицательных числа, дающие в сумме N: необходимое количество самолетов "тонкой" и "толстой" модификаций. Если существует несколько решений, выведите то, в котором количество самолетов "тонкой" модификации максимально. Если решения не существует, выведите два нуля через пробел.

Ограничения

1 ≤ N, P ≤ 109

1 ≤ a1 ≤ b1 < a2 ≤ b2 ≤ 109

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

Входной файл (input.txt) Выходной файл (output.txt)
1
10 50 2 4 7 10
8 2
2
10 200 2 4 7 10
0 0

Задача T. Дерево Штерна-Броко

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

Условие

Один из способов построения множества всех неотрицательных несократимых дробей вида m / n называется деревом Штерна-Броко.

Начнем с дробей 0/1 и 1/0, а затем будем повторять следующую операцию: вставить дробь (m + m′) / (n + n′) между двумя соседними дробями m / n и m′ / n.

Например первый шаг дает одну новую дробь между 0/1 и 1/0: 0/1, 1/1, 1/0. Следующий шаг добавляет две дроби, получая 0/1, 1/2, 1/1, 2/1, 1/0. Весь процесс можно представить в виде бесконечного бинарного дерева (см. рисунок).

Воспользуемся символами L и R для обозначения левой и правой ветвей при продвижении от корня вниз к определенной дроби. Тогда строка символов L и R однозначно определяет местоположения дроби в дереве. Например, строка LRRL соответствует дроби 5/7.

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

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

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

Выходной файл должен содержать строку, являющаяся представлением дроби в дереве Штерна-Броко.

Ограничения

1 ≤ N, M ≤ 105; N ≠ M

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

Входной файл (input.txt) Выходной файл (output.txt)
1
5 7
LRRL

Задача U. Автостоянка на улице Кантора

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

Условие

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

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

013610
24711
5812
913
14

Координаты каждого места на стоянке определяются числами (x; y), где x — количество мест, расположенных западнее данного, y — количество мест, расположенных севернее. Например, место номер 7 имеет координаты (2; 1).

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

Рекомендуется рассмотреть частичные решения

N = 1

C ≤ 106

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

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

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

Выходной файл должен содержать N пар чисел xi yi — координаты мест, соответствующие номерам во входном файле.

Ограничения

1 ≤ N ≤ 105

0 ≤ Ci ≤ 109

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

Входной файл (input.txt) Выходной файл (output.txt)
1
1
1
1 0
2
2
20101204
226
6106 234
4 16

Задача U. Лекция. Простейшие сортировки

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

Условие

Перестановкой конечного множества называется некоторое расположение его элементов в ряд, при этом порядок их следования играет роль. Пусть (r1, r2, ..., rn) — перестановка множества {r1, r2, ..., rn}

Пусть надо упорядочить по возрастанию n элементов r1,...,rn. Будем называть эти элементы записями (records). Каждая запись ri обладает ключом ki, который используется для упорядочивания (или, иначе, сортировки). Помимо ключа, запись может содержать любую другую сопутствующую информацию, не влияющую на порядок записей. Запись может состоять только из ключа, например, если r1,...,rn — числа или строки.

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

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

  1. закон трихотомии: ∀ a, b справедливо одно и только одно из отношений a R b, a = b, b R a
  2. транзитивности: ∀ a, b, c: a R b, b R c⇒ a R c

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

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

Некоторые задачи, решаемые сортировками:

Сортировка вставками
Элементы просматриваются по одному, и каждый новый элемент просеивается (продвигается) влево в подходящее место среди уже отсортированных элементов. В самом начале процесса сортировки множество уже упорядоченных элементов пусто. После первого шага это множество состоит из одного элемента — первого. На втором шаге к нему добавляется второй элемент, продвигаясь при этом в самое начало списка в случае, если он меньше первого. Таким образом на i-м шаге элементы 1.. i − 1 упорядочены относительно друг друга.

Cортировка пузырьком
Еще один способ сортировки: сравнить ключи k1 и k2, и в случае, если k2 < k1, поменять местами записи r2 и r1. То же сделать для r2 и r3 и т.д. для rj и rj + 1. При таком способе сортировки записи с наибольшими ключами будут продвигаться вправо. После первого прохода наибольшая запись займет позицию n, на следующих проходах соответственно n − 1, n − 2 и т.д.

Сортировка выбором
Для каждого i = 1,n выполнить поиск минимального элемента на отрезке [i,n] и поменять местами найденную минимальную запись с ri. В другой версии этой сортировки обмен выполняется не после того, как найден минимум, а в тот же момент, как очередной rj оказывается меньше ri. По сути, это более лаконичный поиск минимума, но он может потребовать большее количество обменов, чем в первом варианте.

Для каждого элемента нужно выполнить поиск минимума среди элементов справа от него. Количество операций сравнения пропорционально количеству сочетаний из n по 2  = n(n − 1)2 ≈ n2.


Задача V. Предусмотрительное жюри

Автор:Кировская командная олимпиада 2001 года   Ограничение времени:5 сек
Входной файл:c.in   Ограничение памяти:64 Мб
Выходной файл:c.out  

Условие

Из правил проведения студенческого командного чемпионата мира по программированию ACM:

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

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

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

Задача:

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

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

Среди членов жюри есть тренер этой команды. Он прознал про тактику, которой решила придерживаться команда, а также может примерно оценить время, которое потребуется команде для решения каждой задачи. Жюри прекрасно понимает, что уже никак не может повлиять на число решенных командой задач, но зато, учитывая тактику команды, жюри может влиять на штрафное время, которое получит команда, располагая задачи в разном порядке. В самом деле, если на тур предлагается две задачи, и на решение одной из них команда тратит 10 минут, а на решение второй - 20, то штрафное время команды, если задачи расположить именно в таком порядке, будет равно 40 минутам (первую задачу команда сдает на 10-й минуте тура, вторую - на 30, 10+30=40). Если же задачи расположить в обратном порядке, то штрафное время будет равно 50 (сначала команда потратит 20 минут, потом еще 10, то есть пошлет задачи на 20-й и 30-й минутах, и штрафное время будет равно 20+30=50).

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

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

Во входном файле записано сначала число N — количество задач на тур. Затем идет N натуральных чисел, каждое из которых не превышает 300. i-ое из этих чисел задает количество минут, которое (по прогнозу тренера) команда "Super solvers" потратит на решение задач номер i.

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

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

Ограничения

1 ≤ N ≤ 20

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

Входной файл (c.in) Выходной файл (c.out)
1
1
25
1
2
2
20 
10
1 2
3
2
10 20
2 1

Задача W. Фонари

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

Условие

На улице длиной в 100 метров установлено N фонарей высотой y1, y2, …, yN метров на расстоянии x1, x2, … xN метров от начала улицы. Форма отражателей такова, что свет каждого фонаря распространяется в пределах конуса с углом при вершине 90°.

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

Рекомендуется рассмотреть частичные решения:

  1. N ≤ 2

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

Во входном файле содержится число N, за которым следует N пар целых чисел x1 y1 x2 y2… xN yN.

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

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

Ограничения

1 ≤ N, yi ≤ 100, 0 ≤ xi ≤ 100.

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

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

Задача X. Быстрая помощь

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

Условие

В городе В случилась катастрофа: неожиданно наступила зима. Чтобы облегчить судьбу жителей В, из города М решено направить N самолётов с тёплой одеждой.

Самолёты имеют различную скорость, так что самолёт номер i затратит на полёт в точности ai минут. Разгрузка любого самолёта в аэропорту В занимает L минут, после чего аэропорт готов к приёму следующего самолёта.

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

Самолёты могут взлетать в любом порядке, но не должны обгонять друг друга в воздухе, т. е. если самолёт 1 взлетел раньше самолёта 2, то и приземлиться он должен раньше.

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

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

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

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

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

Ограничения

1 ≤ N ≤ 10000; 1 ≤ ai, L ≤ 1000

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

Входной файл (input.txt) Выходной файл (output.txt)
1
2 10
8 5
25

Задача Y. Кусочно-линейная функция

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

Условие

Вася хочет построить алгоритм рисования графиков функций вида y = k1|x + b1| + k2|x + b2| + ...  + kn|x + bn|. Он понял, что это график кусочно-линейной функции, т.е. ось x можно разбить на интервалы ненулевой длины так, что на каждом из них график представляет из себя график линейной функции. А линейные функции алгоритм Васи рисовать уже умеет. Вася просит вас помочь ему определить, из каких линейных функций будет состоять его график.

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

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

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

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

Линейные функции должны быть перечислены в порядке возрастания соответствующих им интервалов оси x.

Ограничения

1 ≤ n ≤ 1000.

|ki|, |bi| ≤ 1000

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

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

1.377s 0.012s 63