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

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

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

( Yeskendir Sultanov )

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

можете оставить ссылку на тестировщика эту задачу?

Посмотреть в олимпиаде -> найти задачу -> решить

да я знаю как отправить но мне нужны тесты, можете ли оставить ссылку на тестов?

такой ссылки нет. Тесты нам предоставил temirulan

по вашей последней отправки видно что у вас time limit. У вас решение $N^2$

официальное решение предпологает $NlogN$.  Решается через бинпоиск

пока пользователи не могут смотреть тесты если будет WA или TL.

можно получить авторское решение?

Почему у меня все тесты правильные а там пишет что 1 тест не правильный можно ли узнать какая программа компилируют задачу?

показать/скрыть код

n_and_k = list(map(int, input().split()))
massiv = [int(i) for i in input().split()]
massiv_pack=[]
for i in range(len(massiv)):
    for j in range(i+1,len(massiv)):
        massiv_pack.append(massiv[i]+massiv[j])
print(sorted(massiv_pack)[n_and_k[1]-1])

C++

Copy

#include <bits/stdc++.h>

using namespace std;

int main(){

int n, k;

cin >> n >> k;

int a[n];

vector<int> b;

for(int i = 0; i<n; i++){

cin >> a[i];

}

for(int i = 0; i<n-1; i++){

for(int j = i+1; j<n; j++){

b.push_back(a[i]+a[j]);

}

}

sort(b.begin(), b.end());

cout << b[k-1];

}

#include <bits/stdc++.h>

#define ll long long

#define f first

#define s second

#define mp make_pair

#define pb push_back

using namespace std;

const ll inf = 1e9 + 123;

const ll N = 1e5 + 123;

const ll mod = 1e9 + 7;

ll n,k,a[N];

ll get(int x){

ll cnt = 0;

for(int j = 1; j <= n; ++j){

int l = 1, r = j - 1, ind = 0;

while(l <= r){

int mid = (l + r) / 2;

if(a[mid] + a[j] <= x){

ind = mid;

l = mid + 1;

} else {

r = mid - 1;

}

}

cnt += ind;

}

return cnt;

}

int main() {

cin >> n >> k;

for(int i = 1; i <= n; ++i){

cin >> a[i];

}

sort(a + 1, a + n + 1);

ll l = 0, r = 2000000, ans;

while(l <= r){

ll mid = (l + r) / 2;

if(get(mid) >= k){

ans = mid;

r = mid - 1;

} else {

l = mid + 1;

}

}

cout << ans;

}

показать/скрыть код

from itertools import combinations

n, k = map(int, input().split())



# lst = sorted(map(int, input().split()))
comb_list = sorted(combinations((map(int, input().split())), 2),
                   key=lambda x: (x[0] + x[1]))
print(sum(comb_list[k - 1]))

Java

Copy

Не знаю разрешены ли библиотеки, но эта встроенная