Yeskendir Sultanov


Задача №1. (k-я пара) Вам задан массив $a$, состоящий из $n$ целых чисел $a_1$, $a_2$, ..., $a_n$.
Два элемента массива $a_i$, $a_j$ с индексами $(i, j)$ $1 \le i < j \le n$, могут образовать пару и силой этой пары назовем $a_i + a_j$. Найдите силу пары, являющейся $k$-й по счету, если отсортировать все пары по неубыванию силы.
Формат входных данных:
В первой строке заданы два целых числа $n$ и $k$ ($1 \le k \le \frac{n * (n - 1)}{2}$).
Во второй строке через пробел заданы целые числа $a_1$, $a_2$, ..., $a_n$ ($0 \le a_i \le 10^6$).
Формат выходных данных:
Выведите ответ на задачу.
Примеры:
1.Вход:
3 3
7 1 4
Ответ:
11
2.Вход:
5 7
1 5 3 5 3
Ответ:
8
3.Вход:
10 32
0 0 0 0 0 0 0 0 0 0
Ответ:
0
4.Вход:
9 15
5 6 3 0 0 4 1 4 1
Ответ:
5
Замечание:
В первом примере можно сделать три пары с силами {$a_1$ + $a_2$, $a_1$ + $a_3$, $a_2$ + $a_3$} = {7 + 1, 7 + 4, 1 + 4} = {8, 11, 5}. Если их отсортировать по неубыванию силы, то получится {5, 8, 11} и третий элемент это 11.
Во втором примере можно сделать десять пар с силами {$a_1$ + $a_2$, $a_1$ + $a_3$, $a_1$ + $a_4$, $a_1$ + $a_5$, $a_2$ + $a_3$, $a_2$ + $a_4$, $a_2$ + $a_5$, $a_3$ + $a_4$, $a_3$ + $a_5$, $a_4$ + $a_5$} = {1 + 5, 1 + 3, 1 + 5, 1 + 3, 5 + 3, 5 + 5, 5 + 3, 3 + 5, 3 + 3, 5 + 3} = {6, 4, 6, 4, 8, 10, 8, 8, 6, 8}. Если их отсортировать по неубыванию силы, то получится {4, 4, 6, 6, 6, 8, 8, 8, 8, 10} и седьмой элемент это 8.
Система оценки:
Задача содержит 50 тестов, каждая из которых весят 2 балла.
Ограничения которые присутствуют в тестах:
( Yeskendir Sultanov )
комментарий/решение олимпиада
Задача №2. (k-я пара) Вам задан массив $a$, состоящий из $n$ целых чисел $a_1$, $a_2$, ..., $a_n$.
Два элемента массива $a_i$, $a_j$ с индексами $(i, j)$ $1 \le i < j \le n$, могут образовать пару и силой этой пары назовем $a_i + a_j$. Найдите силу пары, являющейся $k$-й по счету, если отсортировать все пары по неубыванию силы.
Формат входных данных:
В первой строке заданы два целых числа $n$ и $k$ ($1 \le k \le \frac{n * (n - 1)}{2}$).
Во второй строке через пробел заданы целые числа $a_1$, $a_2$, ..., $a_n$ ($0 \le a_i \le 10^6$).
Формат выходных данных:
Выведите ответ на задачу.
Примеры:
1.Вход:
3 3
7 1 4
Ответ:
11
2.Вход:
5 7
1 5 3 5 3
Ответ:
8
3.Вход:
10 32
0 0 0 0 0 0 0 0 0 0
Ответ:
0
4.Вход:
9 15
5 6 3 0 0 4 1 4 1
Ответ:
5
Замечание:
В первом примере можно сделать три пары с силами {$a_1$ + $a_2$, $a_1$ + $a_3$, $a_2$ + $a_3$} = {7 + 1, 7 + 4, 1 + 4} = {8, 11, 5}. Если их отсортировать по неубыванию силы, то получится {5, 8, 11} и третий элемент это 11.
Во втором примере можно сделать десять пар с силами {$a_1$ + $a_2$, $a_1$ + $a_3$, $a_1$ + $a_4$, $a_1$ + $a_5$, $a_2$ + $a_3$, $a_2$ + $a_4$, $a_2$ + $a_5$, $a_3$ + $a_4$, $a_3$ + $a_5$, $a_4$ + $a_5$} = {1 + 5, 1 + 3, 1 + 5, 1 + 3, 5 + 3, 5 + 5, 5 + 3, 3 + 5, 3 + 3, 5 + 3} = {6, 4, 6, 4, 8, 10, 8, 8, 6, 8}. Если их отсортировать по неубыванию силы, то получится {4, 4, 6, 6, 6, 8, 8, 8, 8, 10} и седьмой элемент это 8.
Система оценки:
Задача содержит 50 тестов, каждая из которых весят 2 балла.
Ограничения которые присутствуют в тестах:
( Yeskendir Sultanov )
комментарий/решение(4) олимпиада