Пернехан Утемуратов


Задача №1. 

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

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

Из всевозможных разбиений, какое самое высокое и самое низкое место может занять команда Аманчика. Аманчик участник под номером 1.
Входные данные:
Первая строка входных данных содержит целое число $N$. Следующая строка содержит $2 \cdot N$ целых чисел $1 \le a_i \le 10^5$, $1 \le i \le 2 \cdot N$, разделенных пробелами.
Выходные данные:
Выведите два числа самое высокое и самое низкое место.
Примеры:
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) то команда Аманчика возьмет второе место. Из всевозможных разбиений, указанные выше будут соответствовать самым высоким и самым низким местам.
Оценивание:
Данная задача содержит четыре подзадачи:
$1 \le N \le 3$. Оценивается в $7$ баллов.
$1 \le N \le 6$. Оценивается в $19$ баллов.
$1 \le N \le 2500$. Оценивается в $31$ балл.
$1 \le N \le 10^5$. Оценивается в $43$ балла.
Каждая следующая подзадача оценивается только при прохождении всех предыдущих. ( Пернехан Утемуратов )
комментарий/решение олимпиада
Задача №2. 

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

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

Из всевозможных разбиений, какое самое высокое и самое низкое место может занять команда Аманчика. Аманчик участник под номером 1.
Входные данные:
Первая строка входных данных содержит целое число $N$. Следующая строка содержит $2 \cdot N$ целых чисел $1 \le a_i \le 10^5$, $1 \le i \le 2 \cdot N$, разделенных пробелами.
Выходные данные:
Выведите два числа самое высокое и самое низкое место.
Примеры:
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) то команда Аманчика возьмет второе место. Из всевозможных разбиений, указанные выше будут соответствовать самым высоким и самым низким местам.
Оценивание:
Данная задача содержит четыре подзадачи:
$1 \le N \le 3$. Оценивается в $7$ баллов.
$1 \le N \le 6$. Оценивается в $19$ баллов.
$1 \le N \le 2500$. Оценивается в $31$ балл.
$1 \le N \le 10^5$. Оценивается в $43$ балла.
Каждая следующая подзадача оценивается только при прохождении всех предыдущих. ( Пернехан Утемуратов )
комментарий/решение олимпиада