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

10-11 класс


(k-шы жұп) Сізге n бүтін a1, a2, ..., an сандардан тұратын a массиві берілген.
Массивтің (i,j) 1i<jn индекстері арқылы ai, aj жұбын ала аламыз және ол жұптың күші ai+aj болады. Берілген массивтегі алуға болатын жұптардың барлығын күші бойынша \textbf{кемімейтін} ретпен сұрыптаған кездегі k-шы орындағы жұптың күшінің мәнін табыңыз.
Кіріс деректер форматы:
Бірінші қатарда екі n және k (1kn(n1)2) сандары берілген.
Екінші қатарда бос орын арқылы a1, a2, ..., an (0ai106) бүтін сандары берілген.
Шығыс деректер форматы:
Есептің жауабын шығарыңыз.
Мысалдар:
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
Түсініктеме:
Бірінші мысалда күштері {a1 + a2, a1 + a3, a2 + a3} = {7 + 1, 7 + 4, 1 + 4} = {8, 11, 5} болатын үш жұп алуға болады. Егер оларды күші бойынша кемімейтін ретпен сұрыптасақ, онда олар {5, 8, 11} ретпен тұрады және осындағы 3-шісі 11-ге тең.
Екінші мысалда күштері {a1 + a2, a1 + a3, a1 + a4, a1 + a5, a2 + a3, a2 + a4, a2 + a5, a3 + a4, a3 + a5, a4 + a5} = {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} ретпен тұрады және осындағы 7-шісі 8-ге тең.
Бағалау:
Есеп 50 тесттен тұрады, әр тест 2 ұпаіға бағаланады.
Тесттердегі шектеулер:
( Yeskendir Sultanov )
посмотреть в олимпиаде

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

  -1
7 года 2 месяца назад #

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

  0
7 года 2 месяца назад #

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

  -2
7 года 2 месяца назад #

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

  -1
7 года 2 месяца назад #

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

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

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

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

  0
7 года 2 месяца назад #

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

  -2
6 года 4 месяца назад #

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

пред. Правка 2   0
4 года 3 месяца назад #

  13
4 года 1 месяца назад #

кодты корсету/жасыру

C++

  0
3 года 4 месяца назад #

#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];

}

  0
3 года 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;

}

  0
2 года 2 месяца назад #

кодты корсету/жасыру

Java

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