Editorial for Trại hè Đà Lạt 2020 - Ghép số
Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.
Author:
Ta thấy số lượng chữ số sau khi ghép của mọi cách là như nhau, nên để số sau khi ghép có giá trị lớn nhất thì các số ở phía đầu phải lớn nhất , hay nói cách khác khi ghép ~a_i~ và ~a_j~, ~a_i~ sẽ đứng trước ~a_j~ nếu ~a_i+a_j > a_j+a_i~. Vì vậy, ta sắp xếp các phần tử và in ra theo thứ tự trên.
Code tham khảo
#include <bits/stdc++.h>
using namespace std;
/***Crazy Macros***/
#define all(x) begin(x), end(x)
#define rall(x) x.rbegin(), x.rend()
#define reu(i,a,b) for(ll i = (a); i <= (b); ++i)
#define red(i,a,b) for(ll i = (a); i >= (b); --i)
typedef int64_t ll;
typedef deque<int> di;
typedef deque<ll> dll;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef pair<ll,ll> pll;
typedef pair<int,int> pii;
typedef vector<pii> vii;
typedef tuple<ll,ll,ll> iii;
const ll inf = 2e9;
/***Common Functions***/
ll inp() {ll x; cin >> x; return x;}
string inp_str() {string x; cin >> x; return x;}
ll sqr(ll n) {return n*n;}
ll power(ll a, ll b, ll mod = inf) {
ll res = 1; a %= mod;
for(ll i = b; i > 0; i /= 2) {
if (i % 2) res = (res*a) % mod;
a = (a*a) % mod;
} return res;
}
ll gcd(ll a, ll b) {
while (b > 0) {ll tmp = a % b; a = b; b = tmp;}
return a;
}
bool is_pal(string s) {return equal(all(s), s.rbegin());}
void fast_io() {ios::sync_with_stdio(0); cin.tie(0);}
void file_io(char *in, char *out) {
freopen(in, "r", stdin);
freopen(out, "w", stdout);
}
void print_bool(bool a) {
if (a) cout << "YES\n";
else cout << "NO\n";
}
/***Main Code***/
ll n;
vector<string> a;
void Input() {
cin >> n;
a.clear();
a.resize(n+1);
generate(1+all(a), inp_str);
}
bool cmp(string a, string b) {
return a+b > b+a;
}
void Solve() {
sort(1+all(a), cmp);
for(auto v : a) cout << v;
}
int main()
{
fast_io();
// file_io("MAXV.INP", "MAXV.OUT");
Input(), Solve();
return 0;
}
Comments