#1987

Игра

Темы: [Алгоритмы сортировки]

Источники: [ Личные олимпиады, Московская олимпиада школьников, 7-9 классы, 2010, Задача C ]

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

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

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

Входные данные

Сначала вводятся N, M (1 ≤ N ≤ 1000, 1 ≤ M ≤ 1000). Далее идут N чисел, причём i-е равно количеству очков здоровья, восстанавливаемых бутылкой из i-го кармана пояса. Далее – M чисел, j-е из которых равно количеству очков здоровья, восстанавливаемых бутылкой из j-й ячейки сундука. Все очки – натуральные числа, не превосходящие 10000.

Выходные данные

Вначале выведите K – количество операций обмена. Оно не должно превышать 100000. Далее выведите K пар чисел, описывающих, какие бутылки нужно поменять: первое из чисел от 1 до N – задает номер кармана на поясе, второе – от 1 до M – номер ячейки в сундуке. Если существует более одного варианта, выведите любой.

Примечание

Возможный правильный ответ на первый пример
1
1 2
Возможный правильный ответ на второй пример
2
1 2
2 1
"Ответы", записанные ниже, являются служебной информацией для проверяющей системы.

Примеры

Входные данные

1 2
1
2 3

Выходные данные

Входные данные

2 2
3 1
4 5

Выходные данные

#1988

Строительство школы

Темы: [Цикл for]

Источники: [ Личные олимпиады, Московская олимпиада школьников, 7-9 классы, 2010, Задача D ]

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

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

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

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

Входные данные

Сначала вводится число N — количество учеников (0 < N < 100001). Далее идут в строго возрастающем порядке координаты домов учеников — целые числа, не превосходящие 2∙10⁹ по модулю.

Выходные данные

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

Примеры

Входные данные

4
1 2 3 4

Выходные данные

Входные данные

3
-1 0 1

Выходные данные

#1989

Поклейка обоев

Темы: [Вычислительная геометрия]

Источники: [ Личные олимпиады, Московская олимпиада школьников, 7-9 классы, 2010, Задача E ]

Однажды майор Пронин затеял в квартире ремонт. В одной из стен на кухне по плану потребовалось последовательно проделать (N–1) прямоугольных вентиляционных отверстий с горизонтальными и вертикальными сторонами (0 < N < 101). Если оказывалось, что очередное отверстие пересекается с уже проделанными, то майор вырезал только нетронутую часть соответствующего прямоугольника.

Следующая стадия после ремонта – это поклейка обоев. В магазине напротив майор может заказать не более (2N–1)² прямоугольных кусков обоев любых размеров c ненулевой площадью. Он хочет обклеить стену кусками обоев так, чтобы:

1. Вентиляционные отверстия не были заклеены даже частично.

2. Никакие два куска не пересекались (касаться сторонами они при этом могут).

На стене не осталось бы непокрытой области.

Рассмотрим декартову систему координат, оси которой параллельны сторонам отверстий и стены.

Входные данные

Сначала вводится число N (0 < N < 101), далее – описание N прямоугольников. Первый прямоугольник описывает положение стены в нашей системе координат, остальные (N–1) ― положения отверстий в порядке их появления. Стороны всех прямоугольников параллельны осям координат. Каждый прямоугольник задаётся координатами своих левого нижнего и правого верхнего углов: x₁, y₁, x₂, y₂. Координаты — целые числа, не превосходящие по модулю 31000, x₁ < x₂, y₁ < y₂.

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

Выходные данные

Вначале выведите количество кусков обоев K, которое нужно заказать в магазине (K должно быть не больше (2N–1)²). Далее выведите схему поклейки: K прямоугольников, обозначающих места расположения заказанных кусков. Для каждого прямоугольника нужно вывести координаты его левого нижнего и правого верхнего углов. Все координаты должны быть целыми числами. Гарантируется, что решение существует.

Если возможных способов несколько, выведите любой.

Примеры

Входные данные

2
-1 -1 2 2
0 0 1 1

Выходные данные

#3290

Распродажа (6-9)

Источники: [ Личные олимпиады, Московская олимпиада школьников, 6-9 классы, 2011, Задача A ]

Магазины в рекламных целях часто устраивают распродажи. Так, например, одна из крупных сетей магазинов канцелярских товаров объявила два рекламных предложения: "купи \(N\) одинаковых товаров и получи еще один товар бесплатно" и "купи \(K\) товаров по цене \(K-1\) товара".

Для проведения олимпиады организаторам требуется распечатать условия для участников, на что уходит очень много бумаги. Каждая пачка стоит \(B\) рублей. Какое максимальное количество пачек бумаги можно приобрести на \(A\) рублей, правильно используя рекламные предложения?

Входные данные

Во входном файле записаны целые числа \(N\), \(K\), \(A\) и \(B\) (\(1\leq N\leq 100\), \(2\leq K\leq 100\), \(1\leq A \leq 10000\), \(1\leq B \leq 10000\)), разделенные пробелами.

Выходные данные

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

Примечание

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

Во втором примере рекламными предложениями воспользоваться нельзя.

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

Примеры

Входные данные

4 4 13 2

Выходные данные

Входные данные

3 4 8 3

Выходные данные

Входные данные

3 4 7 1

Выходные данные

#3291

Распродажа (10-11)

Темы: [Жадный алгоритм] [Условный оператор (if)]

Источники: [ Личные олимпиады, Московская олимпиада школьников, 10-11 классы, 2011, Задача A ]

Магазины в рекламных целях часто устраивают распродажи. Так, например,одна из крупных сетей магазинов канцелярских товаров объявила два рекламных предложения: "купи \(N\) одинаковых товаров и получи еще один товар бесплатно"и "купи \(K\) товаров по цене \(K-1\) товара".

Для проведения олимпиады организаторам требуется распечатать условия для участников, на что уходит очень много бумаги. Каждая пачка стоит \(B\) рублей. Какое максимальное количество пачек бумаги можно приобрести на \(A\) рублей, правильно используя рекламные предложения?

Входные данные

Во входном файле записаны целые числа \(N\), \(K\), \(A\) и \(B\) (\(1\leq N\leq 100\), \(2\leq K\leq 100\), \(1\leq A \leq 10^9\), \(1\leq B \leq 10^9\)), разделенные пробелами.

Выходные данные

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

Примечание

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

Во втором примере рекламными предложениями воспользоваться нельзя.

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

Примеры

Входные данные

4 4 13 2

Выходные данные

Входные данные

3 4 8 3

Выходные данные

Входные данные

3 4 7 1

Выходные данные