Codeforces

A. Average Height

Sayaka Saeki is a member of the student council, which has 𝑛 other members (excluding Sayaka). The $𝑖$-th member has a height of $𝑎_𝑖$ millimeters.

It’s the end of the school year and Sayaka wants to take a picture of all other members of the student council. Being the hard-working and perfectionist girl as she is, she wants to arrange all the members in a line such that the amount of photogenic consecutive pairs of members is as large as possible.

A pair of two consecutive members $𝑢$ and $𝑣$ on a line is considered photogenic if their average height is an integer, i.e. $\frac{𝑎_𝑢+𝑎_𝑣}{2}$ is an integer.

Help Sayaka arrange the other members to maximize the number of photogenic consecutive pairs.

Input

The first line contains a single integer $𝑡$ $(1≤𝑡≤500)$ — the number of test cases.

The first line of each test case contains a single integer $𝑛$ $(2≤𝑛≤2000)$ — the number of other council members.

The second line of each test case contains $𝑛$ integers $𝑎_1, 𝑎_2, …, 𝑎_𝑛$ $(1≤𝑎_𝑖≤2⋅10^5)$ — the heights of each of the other members in millimeters.

It is guaranteed that the sum of $𝑛$ over all test cases does not exceed 2000.

Output

For each test case, output on one line $𝑛$ integers representing the heights of the other members in the order, which gives the largest number of photogenic consecutive pairs. If there are multiple such orders, output any of them.

풀이

코드

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
const char nl = '\n';

void solve() {
    int n; cin >> n;
    vector<int> A, B;
    for (int i = 0; i < n; i++) {
        int x; cin >> x;
        if (x % 2) A.push_back(x);
        else B.push_back(x);
    }
    for (auto& x : A) cout << x << " ";
    for (auto& x : B) cout << k << " ";
    cout << nl;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int t; cin >> t;
    while(t--) solve();
    return 0;
}

B. TMT Document

The student council has a shared document file. Every day, some members of the student council write the sequence TMT (short for Towa Maji Tenshi) in it.

However, one day, the members somehow entered the sequence into the document at the same time, creating a jumbled mess. Therefore, it is Suguru Doujima’s task to figure out whether the document has malfunctioned. Specifically, he is given a string of length $𝑛$ whose characters are all either T or M, and he wants to figure out if it is possible to partition it into some number of disjoint subsequences, all of which are equal to TMT. That is, each character of the string should belong to exactly one of the subsequences.

A string $𝑎$ is a subsequence of a string 𝑏 if $𝑎$ can be obtained from $𝑏$ by deletion of several (possibly, zero) characters.

Input

The first line contains an integer $𝑡$ $(1≤𝑡≤5000)$ — the number of test cases.

The first line of each test case contains an integer $𝑛$ $(3≤𝑛<10^5)$, the number of characters in the string entered in the document. It is guaranteed that $𝑛$ is divisible by $3$.

The second line of each test case contains a string of length $𝑛$ consisting of only the characters T and M.

It is guaranteed that the sum of $𝑛$ over all test cases does not exceed $10^5$.

Output

For each test case, print a single line containing YES if the described partition exists, and a single line containing NO otherwise.

풀이 1

코드

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
const char nl = '\n';

void solve() {
    int n; cin >> n;
    string s; cin >> s;
    int m = 0, t = 0;
    for (int i = 0; i < n; i++) {
        if (s[i] == 'T') t++;
        else m++;
    }
    if (t != m * 2) { cout << "NO\n"; return; }
    deque<char> dq1;
    for (int i = 0; i < n; i++) {
        if (s[i] == 'T') dq1.push_back('T');
        else {
            if (dq1.empty()) {cout << "NO\n"; return; }
            dq1.pop_back();
        }
    }
    deque<char> dq2;
    for (int i = n - 1; i >= 0; i--) {
        if (s[i] == 'T') dq2.push_back('T');
        else {
            if (dq2.empty()) {cout << "NO\n"; return; }
            dq2.pop_back();
        }
    }
    cout << "YES\n";
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int t; cin >> t;
    while(t--) solve();
    return 0;
}

풀이 2

코드

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
const char nl = '\n';
 
bool solve() {
    int n; cin >> n;
    string s; cin >> s;
    vector<int> t, m;
    for(int i = 0; i < n; i++) {
        if(s[i] == 'T') t.push_back(i);
        else m.push_back(i);
    }
    if(t.size() != 2 * m.size()) return false;
    for(int i = 0; i < m.size(); i++) {
        if(m[i] < t[i] || m[i] > t[i + m.size()])
            return false;
    }
    return true;
}
 
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int t; cin >> t;
    while(t--) {
        cout << (solve() ? "YES" : "NO") << '\n';
    }
    return 0;
}

C. The Sports Festival

The student council is preparing for the relay race at the sports festival.

The council consists of $𝑛$ members. They will run one after the other in the race, the speed of member $𝑖$ is $𝑠_𝑖$. The discrepancy $𝑑_𝑖$ of the 𝑖-th stage is the difference between the maximum and the minimum running speed among the first $𝑖$ members who ran. Formally, if $𝑎_𝑖$ denotes the speed of the $𝑖$-th member who participated in the race, then $𝑑𝑖=max(𝑎_1,𝑎_2,…,𝑎_𝑖)−min(𝑎_1,𝑎_2,…,𝑎_𝑖)$.

You want to minimize the sum of the discrepancies $𝑑_1+𝑑_2+⋯+𝑑_𝑛$. To do this, you are allowed to change the order in which the members run. What is the minimum possible sum that can be achieved?

Input

The first line contains a single integer $𝑛$ $(1≤𝑛≤2000)$ — the number of members of the student council.

The second line contains $𝑛$ integers $𝑠_1,𝑠_2,…,𝑠_𝑛$ $(1≤𝑠_𝑖≤10^9)$ – the running speeds of the members.

Output

Print a single integer — the minimum possible value of $𝑑_1+𝑑_2+⋯+𝑑_𝑛$ after choosing the order of the members.

풀이 1

DP - Tabulation (Bottom-Up)

코드

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
const char nl = '\n';

ll dp[2020][2020];

void solve() {
    int n; cin >> n;
    vector<ll> S(n);
    for (int i = 0; i < n; i++) cin >> S[i];
    sort(S.begin(), S.end());
    for (int d = 1; d < n; d++) {
        for (int l = 0; l < n; l++) {
            ll r = l + d;
            if (r >= n) continue;
            dp[l][r] = min(dp[l + 1][r], dp[l][r - 1]) + S[r] - S[l];
        }
    }
    cout << dp[0][n - 1] << nl;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    solve();
    return 0;
}

풀이 2

DP - Memoization (Top-Down)

코드

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
const char nl = '\n';

int n;
int S[2020];
ll D[2020][2020];

ll f(int l, int r) {
    if (l == r) return 0;
    ll& ret = D[l][r];
    if (ret != -1) return ret;
    return ret = min(f(l + 1, r) , f(l, r - 1)) + S[r] - S[l];
}

void solve() {
    cin >> n;
    for (int i = 0; i < n; i++) cin >> S[i];
    memset(D, -1, sizeof(D));
    sort(S, S + n);
    cout << f(0, n - 1) << nl;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    solve();
    return 0;
}

https://codeforces.com/contest/1509