# Codeforces Round #723 (Div. 2)

A. Mean Inequality

Solution:

Code:

int t, n;
int a[105];

int main(){
__;
cin >> t;
while(t --){
cin >> n;
for(int i = 1; i <= 2 * n; i ++){
cin >> a[i];
}
sort(a + 1, a + 2 * n + 1);
for(int i = 1; i <= n; i ++){
cout << a[i] << " " << a[i + n] << " ";
}
cout << endl;
}

return 0;
}


B. I Hate 1111

Solution1:

Code:

int t, n;
int x;
int f[10000];
int v[11] = {0, 11, 111, 1111, 11111, 111111, 1111111, 11111111,  111111111};

int main(){
__;
cin >> t;
while(t --){
cin >> n;
memset(f, 0, sizeof(f));
if(n > 1099)   puts("YES");
else{
for(int i = 1; i <= 8; i ++){
for(int j = v[i]; j <= n; j ++){
f[j] = max(f[j - v[i]] + v[i], f[j]);
}
}
puts(f[n] == n ? "YES" : "NO");
}
}

return 0;
}


Solution2:

11A+111\left( 11*C+D \right) =Z

=11\left( A+111C \right) +111D=Z

Code:

int t, n;

int main(){
__;
cin >> t;
while(t --){
cin >> n;
for(int i = 1; i <= 20; i ++){
if(n % 11 == 0) {
puts("YES");
break;
}
n -= 111;
if(n < 0){
puts("NO");
break;
}
}
}
return 0;
}


C2. Potions (Hard Version)

Solution:

Code:

int n;
ll a[200005];

priority_queue<ll, vector<ll>, greater<ll> > q;

int main(){
__;
cin >> n;
ll sum = 0, res = 0, ans = 0;
for(int i = 1; i <= n; i ++){
cin >> a[i];
q.push(a[i]);
sum += a[i];
res ++;
while(sum < 0){
ll t = q.top();
q.pop();
sum -= t;
res --;
}
ans = max(ans, res);
}
cout << ans << endl;
return 0;
}


D. Kill Anton

Solution:

Code:

int t;
int p[5] = {0, 1, 2, 3, 4};
int a[N], sum[N][4], cnt[N], rk[N];
string s, c = "ANOT";

void solve(){
string ans = "";
int n = s.size();
ll cur = 0;
for(int i = 1; i <= 4; i ++){
sum[0][i] = 0;
cnt[i] = 0;
}
for(int i = 1; i <= n; i ++){
a[i] = c.find(s[i - 1]) + 1;
}

for(int i = 1; i <= 4; i ++){
for(int j = 1; j <= n; j ++){
sum[j][i] = sum[j - 1][i] + (i == a[j]);
cnt[i] = sum[j][i];
}
}

do{
for(int i = 1; i <= 4; i ++)    rk[p[i]] = i;
ll res = 0;
for(int i = 1; i <= n; i ++){
for(int j = 1; j <= 4;j ++){
if(rk[j] > rk[a[i]])    res += sum[i][j];
}
}

if(res >= cur){
cur = res;
ans.clear();
for(int i = 1; i <= 4; i ++){
ans += string(cnt[p[i]], c[p[i] - 1]);
}
}

}while(next_permutation(p + 1, p + 5));

cout << ans << endl;
}

int main(){
__;
cin >> t;
while(t --){
cin >> s;
solve();
}
return 0;
}