Loading [MathJax]/jax/output/SVG/jax.js

Республиканская олимпиада по информатике, 2015 год, 10-11 класс


Задача E. Наурыз Cup 2015

Скоро состоится командное соревнование <<Наурыз Cup 2015>>. Команда должна состоять ровно из двух участников. Аманчик сильно хочет в нем участвовать. Он достал список всех 2N (1N105) участников включая себя. У каждого участника есть свой рейтинг. Рейтинг команды это средний рейтинг двух участников. Чем выше рейтинг команды тем выше его место. Команда занимает место под номером K+1, если есть ровно K команд, рейтинг которых строго больше.

Из всевозможных разбиений, какое самое высокое и самое низкое место может занять команда Аманчика. Аманчик участник под номером 1.
Входные данные:
Первая строка входных данных содержит целое число N. Следующая строка содержит 2N целых чисел 1ai105, 1i2N, разделенных пробелами.
Выходные данные:
Выведите два числа самое высокое и самое низкое место.
Примеры:
1.Вход:
3
999 3 1 2 1000 1
Ответ:
1 2
2.Вход:
1
1540 1433
Ответ:
1 1
3.Вход:
3
100000 100000 100000 100000 100000 100000
Ответ:
1 1
В первом примере если мы разобьем участников следующим образом (999, 2) (3, 1) (1000, 1) то команда Аманчика (999, 2) и команда (1000, 1) возьмут первые места, а команда (3, 1) возьмет третье место. А если мы разобьем следующим образом (999, 1) (1000, 2) (3, 1) то команда Аманчика возьмет второе место. Из всевозможных разбиений, указанные выше будут соответствовать самым высоким и самым низким местам.
Оценивание:
Данная задача содержит четыре подзадачи:
1N3. Оценивается в 7 баллов.
1N6. Оценивается в 19 баллов.
1N2500. Оценивается в 31 балл.
1N105. Оценивается в 43 балла.
Каждая следующая подзадача оценивается только при прохождении всех предыдущих. ( Пернехан Утемуратов )
посмотреть в олимпиаде

Комментарий/решение: