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

Условие

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

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

Ограничения

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

3 5

8

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

Условие

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

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

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

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

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

Ограничения

0 ≤ A, B, C ≤ 1000000

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

40 25 30

5

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

Условие

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

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

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

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

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

Ограничения

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

2 5 3

2

2 4 3

1

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

Условие

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

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

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

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

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

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

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

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

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

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

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

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

Ограничения

1 ≤ M, A, B, C ≤ 10⁶

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

10 5 3 2

37

10 3 3 2

-1

Problem F. Second Best ≡

Statement

Given the sequence of integers A₁, A₂, …, A_N, find a number A_s such that there exists exactly one A_m > A_s, and for all k ≠ m A_k ≤ A_s.

Input file format

Output file format

Constraints

Sample tests

3
1 2 3

2

4
3 3 2 3

-1

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

Условие

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

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

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

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

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

Ограничения

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

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

hello

khoor

z

c

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

Условие

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

Имеется шахматная доска 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

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

8
3 5

#.*.#.#.
.#*#.#.#
#.*.#.#.
.#*#.#.#
**X*****
.#*#.#.#
#.*.#.#.
.#*#.#.#

3 1 2

*.#
X**
*.#

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

Условие

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

1 2 3 4 5 4 3 2 1
1 2 1 2 2 1 2 1

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

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

Ограничения

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

9
1 2 3 4 5 4 3 2 1

0

5
1 2 1 2 2

3
1 2 1

5
1 2 3 4 5

4
4 3 2 1

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

Условие

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

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

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

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

Первая строка входного файла содержит целое число n — количество клавиш на клавиатуре. Вторая строка содержит n целых чисел — c₁, c₂, …, c_n, где c_i — количество нажатий, выдерживаемых i-ой клавишей. Третья строка содержит целое число k — общее количество нажатий клавиш, и последняя строка содержит k целых чисел p_j (1 ≤ p_j ≤ n) — последовательность номеров нажатых клавиш.

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

Ограничения

1 ≤ n ≤ 10⁵

1 ≤ k, c_i ≤ 10⁵

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

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. Усовершенствованный шифр Цезаря ≡

Условие

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

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

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

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

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

Ограничения

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

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

AAAAAAAAAAAAAAAAAAAAAAAAAAAA

BCDEFGHIJKLMNOPQRSTUVWXYZABC

QWERTY

RYHVYE

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

Условие

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

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

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

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

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

Ограничения

1 ≤ N ≤ 100

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

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

3
e
ee
eee

ee

3
aabbee
cyydyyy
xiixiixiii

aabbee
xiixiixiii

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

Условие

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

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

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

Ограничения

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

2

1 2
4 3

3

1 2 3
8 9 4
7 6 5

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

Условие

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

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

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

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

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

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

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

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

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

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

Ограничения

1 ≤ N ≤ 10⁵

1 ≤ a_i ≤ 10⁹

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

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

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

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

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

3
1 2 3

1

5
8 5 6 10 3

5

1
1000000000

1000000000

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

Условие

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

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

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

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

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

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

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

Ограничения

1 ≤ N, K ≤ 10⁴

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

1 3

3 4

3 9

1 4

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

Условие

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

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

Входной файл содержит в единственной строке арифметическое выражение, состоящее из чисел в десятичной системе счисления, знаков  +  (ASCII 43₁₀) и  −  (ASCII 45₁₀). Выражение заканчивается знаком  =  (ASCII 61₁₀).

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

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

Ограничения

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

1+2+3=

6

+100-200+300=

200

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

Условие

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

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

Входной файл содержит в единственной строке арифметическое выражение, состоящее из чисел в десятичной системе счисления a_i, знаков  *  (ASCII 42₁₀) и  /  (ASCII 47₁₀). Выражение заканчивается знаком  =  (ASCII 61₁₀).

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

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

Ограничения

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

6*2/3=

4

1/4/2*8=

8

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

Условие

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

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

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

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

Ограничения

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

1 2

1

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

Условие

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

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

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

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

N ≤ 1000

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

Во входном файле находятся целые числа N P a₁ b₁ a₂ b₂.

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

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

Ограничения

1 ≤ N, P ≤ 10⁹

1 ≤ a₁ ≤ b₁ < a₂ ≤ b₂ ≤ 10⁹

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

10 50 2 4 7 10

8 2

10 200 2 4 7 10

0 0

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

Условие

Один из способов построения множества всех неотрицательных несократимых дробей вида 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 ≤ 10⁵; N ≠ M

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

5 7

LRRL

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

Условие

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

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

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

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

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

N = 1

C ≤ 10⁶

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

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

Ограничения

1 ≤ N ≤ 10⁵

0 ≤ C_i ≤ 10⁹

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

1
1

1 0

2
20101204
226

6106 234
4 16

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

Условие

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

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

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

На множестве ключей должно быть определено отношение порядка 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ортировка пузырьком
Еще один способ сортировки: сравнить ключи k₁ и k₂, и в случае, если k₂ < k₁, поменять местами записи r₂ и r₁. То же сделать для r₂ и r₃ и т.д. для r_j и r_j + 1. При таком способе сортировки записи с наибольшими ключами будут продвигаться вправо. После первого прохода наибольшая запись займет позицию n, на следующих проходах соответственно n − 1, n − 2 и т.д.

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

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

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

Условие

Из правил проведения студенческого командного чемпионата мира по программированию 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
25

1

2
20 
10

1 2

2
10 20

2 1

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

Условие

На улице длиной в 100 метров установлено N фонарей высотой y₁, y₂, …, y_N метров на расстоянии x₁, x₂, … x_N метров от начала улицы. Форма отражателей такова, что свет каждого фонаря распространяется в пределах конуса с углом при вершине 90°.

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

1. N ≤ 2

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

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

Ограничения

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

3
1 1 50 10 51 10

2

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

Условие

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

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

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

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

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

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

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

Ограничения

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

2 10
8 5

25

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

Условие

Вася хочет построить алгоритм рисования графиков функций вида y = k₁|x + b₁| + k₂|x + b₂| + ...  + k_n|x + b_n|. Он понял, что это график кусочно-линейной функции, т.е. ось x можно разбить на интервалы ненулевой длины так, что на каждом из них график представляет из себя график линейной функции. А линейные функции алгоритм Васи рисовать уже умеет. Вася просит вас помочь ему определить, из каких линейных функций будет состоять его график.

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

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

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

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

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

Ограничения

1 ≤ n ≤ 1000.

|k_i|, |b_i| ≤ 1000

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

1
1 1

2
-1 -1
1 1

2
1 2 3 2

2
-4 -8
4 8

2
2 2 -2 2

1
0 0