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

Ответ:

2.Вход:

5 7
1 5 3 5 3

Ответ:

3.Вход:

10 32
0 0 0 0 0 0 0 0 0 0

Ответ:

4.Вход:

9 15
5 6 3 0 0 4 1 4 1

Ответ:

Замечание:

В первом примере можно сделать три пары с силами {

$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 балла.
Ограничения которые присутствуют в тестах:

24 теста: $2 \le n \le 10^3$
26 тестов: $2 \le n \le 10^4$

( Yeskendir Sultanov )
комментарий/решение(14) олимпиада

Задача №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

Ответ:

2.Вход:

5 7
1 5 3 5 3

Ответ:

3.Вход:

10 32
0 0 0 0 0 0 0 0 0 0

Ответ:

4.Вход:

9 15
5 6 3 0 0 4 1 4 1

Ответ:

Замечание:

В первом примере можно сделать три пары с силами {

$a_1$ +

$a_2$ ,

$a_1$ +

$a_3$ ,

$a_2$ +

$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$ +

Система оценки:

Задача содержит 50 тестов, каждая из которых весят 2 балла.
Ограничения которые присутствуют в тестах:

10 тестов: $2 \le n \le 10^3$
20 тестов: $2 \le n \le 10^4$
20 тестов: $2 \le n \le 10^5$

( Yeskendir Sultanov )
комментарий/решение(11) олимпиада