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

(k-сыншы жұп) Сізге $n$ бүтін $a_1$, $a_2$, ..., $a_n$ сандардан тұратын $a$ массиві берілген.
Массивтің $(i, j)$ $1 \le i < j \le n$ индекстері арқылы $a_i$, $a_j$ жұбын ала аламыз және ол жұптың күші $a_i + a_j$ болады. Берілген массивтегі алуға болатын жұптардың барлығын күші бойынша \textbf{кемімейтін} ретпен сұрыптаған кездегі $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} ретпен тұрады және осындағы 3-шісі 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} ретпен тұрады және осындағы 7-шісі 8-ге тең.

Бағалау:

Есеп 50 тесттен тұрады, әр тест 2 ұпаіға бағаланады.
Тесттердегі шектеулер:

• 24 тестте: $2 \le n \le 10^3$
  
• 26 тестте: $2 \le n \le 10^4$
  

( Yeskendir Sultanov )

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

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

#include<iostream> 
#include<vector>
using namespace std;

int main() {
	int n, k, c;
	cin >> n >> k;
	int *a = new int[n + 1];
	vector<int> b;

	for (int i = 1; i <= n; i++) {
		cin >> a[i];
	}

	for (int i = 1; i <= n; i++) {
		for (int j = i + 1; j <= n; j++) {
			b.push_back(a[i] + a[j]);
		}
	}

	for (int i = 0; i < b.size() - 1; i++) {
		for (int j = 0; j < b.size() - i - 1; j++) {
			if (b[j] > b[j + 1]) {
				c = b[j];
				b[j] = b[j + 1];
				b[j + 1] = c;
			}
		}
	}

	cout << b[k - 1];

	return 0;
}

[deleted.]

//TLE 26 test

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

#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;

vector<int>b;
int n,m;
int l=1;

main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    cin>>n>>m;
    int a[n+1];
    for(int i=1;i<=n;i++){
        cin>>a[i];    
	}
	
	for(int i=1;i<=n;i++){
		for(int j=i+1;j<=n;j++){
			b.push_back(a[i]+a[j]);
		}
	}
	sort(b.begin(),b.end());
	cout<<b[m-1];
	}

попробуйте использовать scanf и не используйте vector а простой массив

[deleted.]

[deleted.]

[deleted.]

Нет такое решение не пройдет.

Полное решение предполагает использование бинпоиска по ответу.

Отсортируем числа. Для конкретной суммы C посчитаем сколько таких, что $a_i + a_j < C$. это делается за линию.

Если переберем С бинпоиском получим асимптотику  $N * log(max(2 * a_i))$

[deleted.]

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

#include <bits/stdc++.h>

using namespace std;
const int N = (int)(1e5 + 123);
const int C = 2*(1e6) + 3;
int a[N] , c[C] , p[C];
int main() {
    int n , k;
    cin >> n >> k;
    for (int i=1; i<=n; i++) cin >> a[i];
    for (int i=1; i<n; i++)
        for (int j=i+1; j<=n; j++) c[a[i] + a[j]]++;
    p[0] = c[0];
    for (int i=1; i<=C; i++) p[i] = p[i-1] + c[i];
    int l = 0 , r = C , mid = 0;
    while (l <= r) {
        mid = (l + r) >> 1;
        if (p[mid] < k)
            l = mid + 1;
        else
            r = mid - 1;
    }
    cout <<l<<endl;
    return 0;
}

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

#include <bits/stdc++.h>
using namespace std;
int n,k;
long long len=0;

int  a[10005], x[49995001];
int main(){
    cin>>n>>k;
    
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
    for(int i=1;i<n;i++){
        for(int j=i+1;j<=n;j++){
            x[len++]=a[i]+a[j];
        }
    }
    sort(x,x+len);
    cout<<x[k-1]<<endl;
}

На питоне

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

def sort_sum(n, a):
    if n < 1:
        return 0
    else:
        global l
        p = a[0]
        for i in range(1, n):
            l.append(p+a[i])
        return sort_sum(n-1, a[1:])
n, k = map(int ,input().split())
a = list(map(int, input().split()))
l = []
sort_sum(n, a)
l.sort()
print(l[k-1])

=#include <bits/stdc++.h>

using namespace std;

signed main(){

ios_base::sync_with_stdio(false);

cin.tie(0);

int n , k;

cin >> n >> k;

priority_queue<int>st;

vector<int>a(n);

for(int i = 0; i < n; ++i)cin >> a[i];

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

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

for(int j = i + 1; j <= min(i + 350 , n - 1); ++j){

if(st.size() < k){

st.push(a[i] + a[j]);

}

else{

if(a[i] + a[j] < st.top()){

st.pop();

st.push(a[i] + a[j]);

}

}

}

}

cout << st.top();

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