Chênh lệch tối đa có thể đạt được bằng cách chọn một nửa số lá bài có giá trị nhỏ nhất cho một người, và phần còn lại được chọn cho người kia.

#include<bits/stdc++.h>
using namespace std;

void solve(){
    int n; cin >> n;
    int a[n];
    for(int &i : a) cin >> i;
    sort(a, a + n);
    int x = 0, y = 0;
    for(int i=0; i<n; i++){
        if(i < n / 2) x += a[i];
        else y += a[i];
    }
    cout << y - x;
}

signed main(){
    cin.tie(0) -> sync_with_stdio(0);
    
    int tc = 1; //cin >> tc;
    while(tc--) solve();
}

Ta sẽ cần sắp xếp lại mảng các số này, tuy nhiên, nếu ta sắp xếp theo thứ tự giảm dần thì rất có thể sẽ gặp phải trường hợp

$$$a = [321, 32] \to 32132$$$ nhưng nó sẽ nhỏ hơn việc ta ghép ngược lại là $$$32321$$$.

Như vậy, ta sẽ cần sắp xếp theo tiêu chí số dứng trước nối với số đứng sau phải lớn hơn phép nối ngược lại.

#include<bits/stdc++.h>
using namespace std;

void solve(){
    int n; cin >> n;
    string a[n];
    for(auto &i : a) cin >> i;
    sort(a, a + n, [](string a, string b){
        return a + b > b + a;
    });
    for(auto &i : a) cout << i;
}

signed main(){
    cin.tie(0) -> sync_with_stdio(0);
    
    int tc = 1; //cin >> tc;
    while(tc--) solve();
}

Ta có nhận xét rằng khi độ chênh lệch là nhỏ nhất thì tức là tập hợp $$$k$$$ phần tử đó là các giá trị gần nhau nhất có thể.

Hay có thể hiểu là khi ta sắp xếp lại mảng $$$a$$$ thì tập hợp đó sẽ là $$$1$$$ trong những đoạn con độ dài $$$k$$$ của mảng.

#include<bits/stdc++.h>
using namespace std;

#define el '\n'

void solve(){
    int n, k; cin >> n >> k;
    int a[n+1];
    for(int i=1; i<=n; i++) cin >> a[i];
    sort(a+1, a+n+1);
    int res = 2e9;
    for(int i=1; i<=n-k+1; i++){
        res = min(res, a[i + k - 1] - a[i]);
    }
    cout << res << el;
}

signed main(){
    cin.tie(0) -> sync_with_stdio(0);
    
    int tc = 1; cin >> tc;
    while(tc--) solve();
}

Đây thực chất là bài toán Nối dây mà các bạn làm ở trên Code PTIT.

Ta có thể tư duy theo hướng ghép lại $$$n$$$ thanh gỗ đó trở lại ban đầu, tức là ghép $$$2$$$ đoạn gỗ dài $$$u$$$ và $$$v$$$ thì sẽ tốn $$$u + v$$$ đơn vị tiền.

#include<bits/stdc++.h>
using namespace std;

#define el '\n'
#define int long long 

void solve(){
    int n; cin >> n;
    priority_queue<int, vector<int>, greater<int>> q;
    for(int i=1; i<=n; i++){
        int x; cin >> x;
        q.push(x);
    }
    int res = 0;
    while(q.size() > 1){
        int x = q.top(); q.pop();
        int y = q.top(); q.pop();
        q.push(x + y);
        res += x + y;
    }
    cout << res << el;
}

signed main(){
    cin.tie(0) -> sync_with_stdio(0);
    
    int tc = 1; //cin >> tc;
    while(tc--) solve();
}

Các giá trị có thể đạt được của biểu thức $$$x$$$ $$$\%$$$ $$$y$$$ là bao nhiêu ?

Đúng, các giá trị sẽ nằm trong đoạn $$$[0, y - 1]$$$. Như vậy để có thể tối đa hoá tập hợp kết quả thì ta sẽ cần làm gì với giá trị $$$y$$$ ?

Đúng, ta sẽ chỉ cần chọn $$$y$$$ là lớn nhất có thể, như vậy $$$y = max(a_1, a_2, ..., a_n)$$$. Vậy còn giá trị $$$x$$$ thì sao ?

Đúng, ta sẽ cần chọn giá trị $$$x$$$ là giá trị lớn thứ hai trong mảng vì khi đó đáp số bài toán sẽ chính là $$$x$$$. Ngoài ra, khi mảng chỉ gồm $$$1$$$ giá trị duy nhất (tức là không có giá trị $$$x$$$), thì đương nhiên đáp số bài toán sẽ là $$$0$$$.

#include<bits/stdc++.h>
using namespace std;

#define el '\n'

void solve(){
    int n; cin >> n;
    int a[n];
    for(int &i : a) cin >> i;
    sort(a, a + n);
    for(int i=n-1; i>0; i--){
        if(a[i] > a[i - 1]){
            cout << a[i - 1];
            return;
        }
    }
    cout << 0;
}

signed main(){
    cin.tie(0) -> sync_with_stdio(0);
    
    int tc = 1; //cin >> tc;
    while(tc--) solve();
}

Giả dụ An sẽ làm hết $$$n \times 2$$$ công việc, vậy thì tổng thời gian giải quyết sẽ là $$$S = \sum\limits_{i = 1}^{n \times 2} a_i$$$. Như vậy, ta cần tham lam sang cho Bình $$$n$$$ công việc sao cho giảm được giá trị $$$S$$$ đi càng nhiều càng tốt.

Vì giá trị $$$S$$$ sẽ thay đổi theo hướng: đổi việc thứ $$$i$$$ từ An thành Bình $$$\to S = S - a_i + b_i = S - (a_i - b_i)$$$, nên ta sẽ cần tạo thêm một mảng lưu các giá trị $$$(a_i - b_i)$$$ và rồi chọn ra đúng $$$n$$$ giá trị lớn nhất.

#include<bits/stdc++.h>
using namespace std;

#define pe pair<int, int>
#define fi first
#define se second
int n;
pe a[1000005];
 
void solve(){
    cin >> n; n *= 2;
    int x = 0;
    for(int i=1; i<=n; i++){
        cin >> a[i].fi >> a[i].se;
        x += a[i].fi;
    }
    sort(a+1, a+n+1, [](pe a, pe b){
        if(a.fi - a.se == b.fi - b.se) return a.se < b.se;
        return a.fi - a.se > b.fi - b.se;
    });
    for(int i=1; i*2<=n; i++){
        x = x - a[i].fi + a[i].se;
    }
    cout << x;
}

signed main(){
    cin.tie(0) -> sync_with_stdio(0);
    
    int tc = 1; //cin >> tc;
    while(tc--) solve();
}

Ta dễ dàng nhận thấy rằng tập con $$$b$$$ không thoả mãn điều kiện đề bài khi và chỉ khi tồn tại $$$2$$$ số $$$x$$$ và $$$y$$$ sao cho:

$$$(x + y)$$$ $$$\%$$$ $$$k = 0$$$ $$$\to$$$ $$$((x$$$ $$$\%$$$ $$$k) + (y$$$ $$$\%$$$ $$$k))$$$ $$$\%$$$ $$$k = 0$$$.

Ta có thể rút ra $$$2$$$ nhận xét là:

• Chia dư mọi phần tử mảng cho $$$k$$$ để dễ xử lý $$$\to$$$ từ giờ coi như các số đã được chia dư cho $$$k$$$.

• Nếu $$$x = i$$$ thì $$$y = k - i$$$, như vậy ta sẽ đếm số lần xuất hiện của các số trong đoạn $$$[0, k - 1]$$$ do khi chia dư thì các kết quả chỉ nằm trong đoạn đó.

Để tập con $$$b$$$ là lớn nhất thì với mỗi cặp $$$(i, k - i)$$$ ta sẽ cần chọn ra giá trị $$$max(cnt[i], cnt[k - i])$$$. Tuy nhiên, có $$$2$$$ giá trị đặc biệt mà ta cần chú ý đó chính là $$$0$$$ và $$$k / 2$$$ (nếu $$$k$$$ là số chẵn). Lí do là bởi vì ta sẽ chỉ có thể sử dụng tối đa $$$1$$$ số $$$0$$$ duy nhất để nhét vào $$$b$$$, cũng như là tối đa $$$1$$$ số $$$k / 2$$$ (nếu $$$k$$$ là số chẵn) để nhét vào $$$b$$$.

#include<bits/stdc++.h>
using namespace std;

int cnt[1005];

void solve(){
    int n, k; cin >> n >> k;
    int a[n+5];
    for(int i=1; i<=n; i++){
        cin >> a[i];
        ++cnt[a[i] % k];
    }
    int res = 0;
    if(cnt[0] > 0) res = 1;
    for(int i=1; i<=k/2; i++){
        if(i < k - i){
            res += max(cnt[i], cnt[k - i]);
        }else if(cnt[i] > 0) ++res;
    }
    cout << res;
}

signed main(){
    cin.tie(0) -> sync_with_stdio(0);
    
    int tc = 1; //cin >> tc;
    while(tc--) solve();
}

// LonggVuz
#include<bits/stdc++.h>
using namespace std;
#define el cout << '\n'
#define inc(i, a, b, c) for(int32_t i=a; i<=b; i+=c)
#define dec(i, a, b, c) for(int32_t i=a; i>=b; i-=c)
#define fo(i, a, b) for(int32_t i=a; i<=b; i++)
#define fd(i, a, b) for(int32_t i=a; i>=b; i--)
#define out(x) return void(cout << (x));
#define all(x) begin(x), end(x)
#define len(x) (int)(x).size()
#define vec vector
#define pub push_back
#define pob pop_back
#define int int64_t

const int mod = 1e9 + 7;
const int oo = 1e18 + 7;
const int mxn = 1e5 + 7;

#define pe pair<int, int>
#define fi first
#define se second
int n, x, y, z, a[mxn], b[mxn];

void LonggVuz(){
    cin >> n >> x >> y >> z;
    vec<pe> v;
    fo(i, 1, n){
        cin >> a[i] >> b[i];
        v.pub({a[i], 1});
        v.pub({b[i], -1});
    }
    sort(all(v), [&](pe u, pe v){
        if(u.fi == v.fi) return u.se > v.se;
        return u.fi < v.fi;
    });
    int cur = 0;
    fo(i, 1, n) cur += x;
    int res = cur;
    for(auto &[i, j] : v){
        if(j > 0){
            cur = cur - x + y;
        }else{
            cur = cur - y + z;
        }
        res = max(res, cur);
    }
    cout << res;
}

signed main(){
    ios::sync_with_stdio(false); cin.tie(nullptr);
    
    signed orz = 1; //cin >> orz;
    while(orz --> 0){
        LonggVuz();
        if(orz) el;
    }
    
    cerr << "Execution Time: " << 0.001 * clock() << "s\n";
}

Thao tác đề bài đã cho có thể giúp ta sắp xếp lại mảng theo cách tuỳ ý. Như vậy, ta cần sắp xếp sao cho các phần tử cách nhau $$$k$$$ đơn vị có giá trị chênh lệch nhau là nhỏ nhất.

Tuy nhiên, để việc chuyển suy nghĩ đó vào code trở nên đơn giản thì ta sẽ sắp xếp lại mảng:

Xét ví dụ $$$1$$$, ta có $$$a = [5, 2, 7, 1, 10, 3] \to a = [1, 2, 3, 5, 7, 10]$$$.

Sau đó, ta sẽ coi $$$1$$$ ở vị trí $$$1$$$, duyệt qua các số ngay phía sau và gán cho nó vị trí $$$1 + k$$$ tức là $$$2$$$ sẽ ở vị trí $$$1 + k$$$. Cứ như vậy thì số $$$3$$$ sẽ ở vị trí $$$1 + k \times 2$$$, tuy nhiên vị trí này đã vượt quá kích thước mảng nên ta sẽ phải coi nó như vị trí $$$2$$$ rồi lại gán tiếp các vị trí $$$2 + k, ...$$$

#include<bits/stdc++.h>
using namespace std;

#define el '\n'
#define int long long 

void solve(){
    int n, k; cin >> n >> k;
    int a[n+5];
    for(int i=1; i<=n; i++){
        cin >> a[i];
    }
    sort(a+1, a+n+1);
    int res = 0, x = n / k;
    for(int i=1; i<=n; i+=x){
        for(int j=i; j<i+x-1; j++){
            res += a[j + 1] - a[j];
        }
    }
    cout << res;
}

signed main(){
    cin.tie(0) -> sync_with_stdio(0);
    
    int tc = 1; //cin >> tc;
    while(tc--) solve();
}

Ta sẽ tách bài toán này thành $$$2$$$ bài toán con là tìm giá trị nhỏ nhất của tổng khoảng cách từ điểm $$$u$$$ đến $$$a_x$$$ và $$$v$$$ đến $$$a_y$$$.

Như vậy, ta sẽ cần biết thêm một nhận xét là trung vị của mảng sẽ là phần tử mà có tổng khoảng cách tới các phần tử trong mảng là nhỏ nhất. Dưới đây là ví dụ minh hoạ:

Đầu tiên là với mảng có độ dài chẵn, ta sẽ xét mảng $$$a = [1, 2, 4, 6, 7, 9]$$$. Trung vị ta chọn sẽ có thể là số $$$4$$$ hoặc số $$$6$$$, lí do là bởi vì nếu ta chọn số bên trái số $$$4$$$ thì sẽ có $$$4$$$ phần tử tăng thêm $$$2$$$ đơn vị khoảng cách, so với $$$2$$$ phần tử được giảm khoảng cách. Tương tự đối với phần tử số $$$6$$$ cũng như vậy. Tiếp theo là với mảng có độ dài lẻ, ta sẽ xét mảng $$$a = [1, 2, 4, 6, 7, 9, 12]$$$. Trung vị duy nhất ta có thể chọn sẽ là số $$$6$$$, cách giải thích cũng sẽ tương tự như phía trên.

Cuối cùng, ta có thể rút ra được nhận xét: trung vị của mảng là phần tử thứ $$$\frac{(n + 1)}{2}$$$ sau khi sắp xếp mảng tăng dần.

#include<bits/stdc++.h>
using namespace std;

void solve(){
    int n; cin >> n;
    int a[n+5], b[n+5];
    for(int i=1; i<=n; i++){
        cin >> a[i] >> b[i];
    }
    sort(a+1, a+n+1);
    sort(b+1, b+n+1);
    int res = 0, x = a[(n + 1) / 2], y = b[(n + 1) / 2];
    for(int i=1; i<=n; i++){
        res += abs(x - a[i]) + abs(y - b[i]);
    }
    cout << res;
}

signed main(){
    cin.tie(0) -> sync_with_stdio(0);
    
    int tc = 1; //cin >> tc;
    while(tc--) solve();
}

// LonggVuz
#include<bits/stdc++.h>
using namespace std;
#define el cout << '\n'
#define inc(i, a, b, c) for(int32_t i=a; i<=b; i+=c)
#define dec(i, a, b, c) for(int32_t i=a; i>=b; i-=c)
#define fo(i, a, b) for(int32_t i=a; i<=b; i++)
#define fd(i, a, b) for(int32_t i=a; i>=b; i--)
#define out(x) return void(cout << (x));
#define all(x) begin(x), end(x)
#define len(x) (int)(x).size()
#define vec vector
#define pub push_back
#define pob pop_back
#define int uint64_t

const int mod = 1e9 + 7;
const int oo = 1e19 + 7;
const int mxn = 1e6 + 7;

int sum(int n){
    int s = 0;
    while(n){
        s += n % 10;
        n /= 10;
    }
    return s;
}

void LonggVuz(){
    int n, s; cin >> n >> s;
    if(sum(n) <= s) out(0);
    int res = oo;
    string a = to_string(n);
    int pre = 0, cur = 0;
    fo(i, 0, len(a) - 1){
        if(a[i] < '9'){
            int sum = pre + (a[i] - '0') + 1;
            if(sum <= s){
                int so = cur;
                so = so * 10 + (a[i] - '0') + 1;
                while(so < n) so *= 10;
                res = min(res, so - n);
            }
        }
        pre += a[i] - '0';
        cur = cur * 10 + a[i] - '0';
    }
    if(res == oo){
        int ans = 1;
        while(ans < n) ans *= 10;
        res = min(res, ans - n);
    }
    cout << res;
}

signed main(){
    ios::sync_with_stdio(false); cin.tie(nullptr);
    
    signed orz = 1; cin >> orz;
    while(orz --> 0){
        LonggVuz();
        if(orz) el;
    }
    
    cerr << "Execution Time: " << 0.001 * clock() << "s\n";
}

Với số phút $$$m$$$ có thể lên tới $$$10^9$$$, ta phải làm cách nào để xác định được hết rằng phút $$$i$$$ sẽ luyện kỹ năng nào ?

Đúng, ta không cần xét hết $$$m$$$ phút, cụ thể hơn là tối đa ta sẽ cần $$$n$$$ phút, lí do là bởi vì khi sử dụng hết lần đầu tiên của các kỹ năng thì ta sẽ chỉ luyện đúng duy nhất $$$1$$$ kỹ năng cung cấp nhiều sức mạnh nhất. Vậy thì chọn kỹ năng như nào cho phù hợp đây ?

Đúng, ta sẽ sử dụng hàng đợi ưu tiên để giải quyết bài toán này. Đầu tiên thì ta sẽ đưa vào các giá trị sức mạnh $$$e_i + s_i$$$ mà phép luyện kỹ năng có thể cung cấp, sau đó mỗi khi lấy phần tử ở đầu ra thì ta sẽ chỉ đưa lại giá trị $$$e_i$$$ vào thôi, do $$$s_i$$$ chỉ nhận được khi lần đầu luyện kỹ năng $$$i$$$ đó.

#include<bits/stdc++.h>
using namespace std;

#define out(x) return cout << x, void()
#define all(x) x.begin(), x.end()
#define len(x) (int)x.size()
#define el '\n'
#define int long long

const int mod = 1e9 + 7;
const int oo = 1e18 + 7;
const int mxn = 1e6 + 7;

#define pe pair<int, int>
#define fi first
#define se second

void solve(){
    int n, m; cin >> n >> m;
    pe a[n+5];
    for(int i=1; i<=n; i++){
        cin >> a[i].fi >> a[i].se;
    }
    priority_queue<pe> q;
    for(int i=1; i<=n; i++){
        q.push({a[i].fi + a[i].se, i});
    }
    int res = 0;
    for(int i=1; i<=min(n, m); i++){
        pe top = q.top(); q.pop();
        int sc = top.fi, id = top.se;
        res += sc;
        q.push({a[id].se, id});
    }
    if(m > n) res += (m - n) * q.top().fi;
    cout << res;
}

signed main(){
    cin.tie(0) -> sync_with_stdio(0);
    
    int tc = 1; //cin >> tc;
    while(tc--) solve();
}

// LonggVuz
#include<bits/stdc++.h>
using namespace std;

#ifdef LOCAL
#include<LonggVuz.h>
#else
#define debug(...)
#endif

#define el cout << '\n'
#define inc(i, a, b, c) for(int32_t i=a; i<=b; i+=c)
#define dec(i, a, b, c) for(int32_t i=a; i>=b; i-=c)
#define fo(i, a, b) for(int32_t i=a; i<=b; i++)
#define fd(i, a, b) for(int32_t i=a; i>=b; i--)
#define out(x) return void(cout << (x));
#define all(x) begin(x), end(x)
#define len(x) (int)(x).size()
#define vec vector
#define pub push_back
#define pob pop_back
#define float double
#define int int64_t

const int mod = 1e9 + 7;
const int oo = 1e18 + 7;
const int mxn = 1e6 + 7;



void LonggVuz(){
    int n; cin >> n;
    string a; cin >> a;
    int i = 0;
    while(i < n){
        if(a[i] != 'C'){
            int j = i;
            while(j < n and a[j] != 'C') ++j;
            sort(a.begin() + i, a.begin() + j);
            i = j;
        }else ++i;
    }
    fo(i, 0, n - 1){
        if(a[i] == 'B' and i + 1 < n and a[i + 1] == 'B'){
            cout << 'A';
            ++i;
        }else cout << a[i];
    }
}

signed main(){
    ios::sync_with_stdio(false); cin.tie(nullptr);
    
    signed orz = 1; if(false) cin >> orz;
    while(orz --> 0){
        LonggVuz();
        if(orz) el;
    }
    
    cerr << "Execution Time: " << clock() << "ms\n";
}

// LonggVuz
#include<bits/stdc++.h>
using namespace std;
#define el cout << '\n'
#define inc(i, a, b, c) for(int32_t i=a; i<=b; i+=c)
#define dec(i, a, b, c) for(int32_t i=a; i>=b; i-=c)
#define fo(i, a, b) for(int32_t i=a; i<=b; i++)
#define fd(i, a, b) for(int32_t i=a; i>=b; i--)
#define out(x) return void(cout << (x));
#define all(x) begin(x), end(x)
#define len(x) (int)(x).size()
#define vec vector
#define pub push_back
#define pob pop_back
#define int int64_t

const int mod = 1e9 + 7;
const int oo = 1e18 + 7;
const int mxn = 1e6 + 7;



void LonggVuz(){
    string a; cin >> a;
    vec<int> cnt(500);
    int res = 0, cur = 0;
    fo(i, 0, len(a) - 1){
        if(a[i] == 'A'){
            if(cnt[23]) --cnt[23], --cur;
            else if(cnt[32]) --cnt[32], --cur;
            else{
                if(cnt[2]){
                    --cnt[2]; ++cnt[21];
                }else if(cnt[3]){
                    --cnt[3]; ++cnt[31];
                }else{
                    ++cnt[1]; ++cur;
                }
            }
        }else if(a[i] == 'B'){
            if(cnt[13]) --cnt[13], --cur;
            else if(cnt[31]) --cnt[31], --cur;
            else{
                if(cnt[1]){
                    --cnt[1]; ++cnt[12];
                }else if(cnt[3]){
                    --cnt[3]; ++cnt[32];
                }else{
                    ++cnt[2]; ++cur;
                }
            }
        }else{
            if(cnt[12]) --cnt[12], --cur;
            else if(cnt[21]) --cnt[21], --cur;
            else{
                if(cnt[1]){
                    --cnt[1]; ++cnt[13];
                }else if(cnt[2]){
                    --cnt[2]; ++cnt[23];
                }else{
                    ++cnt[3]; ++cur;
                }
            }
        }
        res = max(res, cur);
    }
    cout << res;
}

signed main(){
    ios::sync_with_stdio(false); cin.tie(nullptr);
    
    signed orz = 1; //cin >> orz;
    while(orz --> 0){
        LonggVuz();
        if(orz) el;
    }
    
    cerr << "Execution Time: " << 0.001 * clock() << "s\n";
}

// LonggVuz
#include<bits/stdc++.h>
using namespace std;
#define el cout << '\n'
#define inc(i, a, b, c) for(int32_t i=a; i<=b; i+=c)
#define dec(i, a, b, c) for(int32_t i=a; i>=b; i-=c)
#define fo(i, a, b) for(int32_t i=a; i<=b; i++)
#define fd(i, a, b) for(int32_t i=a; i>=b; i--)
#define out(x) return void(cout << (x));
#define all(x) begin(x), end(x)
#define len(x) (int)(x).size()
#define vec vector
#define pub push_back
#define pob pop_back
#define int int64_t

const int mod = 1e9 + 7;
const int oo = 1e18 + 7;
const int mxn = 1e6 + 7;



void LonggVuz(){
    int n, c; cin >> n >> c;
    int a[n+5];
    fo(i, 1, n) cin >> a[i];
    sort(a+1, a+n+1);
    multiset<int> res;
    int ans = 0;
    fd(i, n, 1){
        auto it = res.upper_bound(c - a[i]);
        if(it == res.begin()) res.insert(a[i]), ++ans;
        else{
            --it;
            res.erase(it);
        }
    }
    cout << ans;
}

signed main(){
    ios::sync_with_stdio(false); cin.tie(nullptr);
    
    signed orz = 1; //cin >> orz;
    while(orz --> 0){
        LonggVuz();
        if(orz) el;
    }
    
    cerr << "Execution Time: " << 0.001 * clock() << "s\n";
}

// LonggVuz
#include<bits/stdc++.h>
using namespace std;
#define el cout << '\n'
#define inc(i, a, b, c) for(int32_t i=a; i<=b; i+=c)
#define dec(i, a, b, c) for(int32_t i=a; i>=b; i-=c)
#define fo(i, a, b) for(int32_t i=a; i<=b; i++)
#define fd(i, a, b) for(int32_t i=a; i>=b; i--)
#define out(x) return void(cout << (x));
#define all(x) begin(x), end(x)
#define len(x) (int)(x).size()
#define vec vector
#define pub push_back
#define pob pop_back
#define int int64_t

const int mod = 1e9 + 7;
const int oo = 1e18 + 7;
const int mxn = 1e6 + 7;



void LonggVuz(){
    int n; cin >> n;
    vec<string> v(n);
    for(auto &i : v) cin >> i;
    sort(all(v), [&](string x, string y){
        if(len(x) == len(y)) return x > y;
        return len(x) > len(y);
    });
    vec<string> res;
    fo(i, 0, 2) res.pub(v[i]);
    sort(all(res), [&](string x, string y){
        return x + y > y + x;
    });
    for(auto &i : res) cout << i;
}

signed main(){
    ios::sync_with_stdio(false); cin.tie(nullptr);
    
    signed orz = 1; //cin >> orz;
    while(orz --> 0){
        LonggVuz();
        if(orz) el;
    }
    
    cerr << "Execution Time: " << 0.001 * clock() << "s\n";
}