Codeforces

A. Meximization

You are given an integer $𝑛$ and an array $𝑎_1,𝑎_2,…,𝑎_𝑛$. You should reorder the elements of the array 𝑎 in such way that the sum of 𝐌𝐄𝐗 on prefixes ($𝑖$-th prefix is $𝑎_1,𝑎_2,…,𝑎_𝑖$) is maximized.

Formally, you should find an array $𝑏_1,𝑏_2,…,𝑏_𝑛$, such that the sets of elements of arrays 𝑎 and 𝑏 are equal (it is equivalent to array 𝑏 can be found as an array 𝑎 with some reordering of its elements) and $\sum_{𝑖=1}^𝑛 𝐌𝐄𝐗(𝑏_1,𝑏_2,…,𝑏_𝑖)$ is maximized.

$𝐌𝐄𝐗$ of a set of nonnegative integers is the minimal nonnegative integer such that it is not in the set.

For example, $𝐌𝐄𝐗({1,2,3})=0$, $𝐌𝐄𝐗({0,1,2,4,5})=3$.

Input

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

The first line of each test case contains a single integer $𝑛$ $(1≤𝑛≤100)$.

The second line of each test case contains $𝑛$ integers $𝑎_1,𝑎_2,…,𝑎_𝑛$ $(0≤𝑎_𝑖≤100)$.

Output

For each test case print an array $𝑏_1,𝑏_2,…,𝑏_𝑛$ — the optimal reordering of $𝑎_1,𝑎_2,…,𝑎_𝑛$, so the sum of $𝐌𝐄𝐗$ on its prefixes is maximized.

If there exist multiple optimal answers you can find any.

풀이

0 부터 100 까지 배열을 만든 다음 각 숫자에 맞춰 각 숫자가 몇개 있는지 세어준다. 처음엔 순서대로 0 부터 100 까지 돌면서 숫자가 있으면 출력해주고 하나씩 빼준다. 이후엔 남은 숫자 아무거나 출력해도 되므로 남은 순서대로 다 출력해준다.

코드

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

int A[102];
int vst[102];

void solve() {
    int n; cin >> n;
    memset(vst, 0, sizeof(vst));
    for (int i = 0; i < n; i++) {
        cin >> A[i];
        vst[A[i]]++;
    }
    for (int i = 0; i < 101; i++) {
        if (vst[i] > 0) {
            cout << i << " ";
            vst[i]--;
        }
    }
    for (int i = 0; i < 101; i++) {
        while (vst[i] > 0) {
            cout << i << " ";
            vst[i]--;
        }
    }
    cout << "\n";
}

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

B. M-arrays

You are given an array $𝑎_1,𝑎_2,…,𝑎_𝑛$ consisting of $𝑛$ positive integers and a positive integer $𝑚$.

You should divide elements of this array into some arrays. You can order the elements in the new arrays as you want.

Let’s call an array $𝑚$-divisible if for each two adjacent numbers in the array (two numbers on the positions $𝑖$ and $𝑖+1$ are called adjacent for each $𝑖$) their sum is divisible by $𝑚$. An array of one element is $𝑚$-divisible.

Find the smallest number of $𝑚$-divisible arrays that $𝑎_1,𝑎_2,…,𝑎_𝑛$ is possible to divide into.

Input

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

The first line of each test case contains two integers $𝑛, 𝑚$ $(1≤𝑛≤10^5,1≤𝑚≤10^5)$.

The second line of each test case contains 𝑛integers $𝑎_1,𝑎_2,…,𝑎_𝑛$ $(1≤𝑎_𝑖≤10^9)$.

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

Output

For each test case print the answer to the problem.

풀이

m 의 나머지로 된 배열을 만든 다음 각 숫자에 맞춰 A[i] % m에 대해 몇 개 있는지 세어준다. 숫자가 m이면 하나를 만들 수 있으므로 처음에 세어준다. 이후 1 부터 m 까지 돎면서 B[i]와 B[m - i]에서 두 수가 모두 0이 아니라면 cnt를 1 더하주고 두 수를 비교하여 작은 수는 0으로 만들어주고 큰수는 작은수 + 1 만큼 빼준다. 두 수가 같다면 둘 다 0 으로 만들어준다. 이후 남은 숫자들에 대해 cnt를 더해준다.

코드

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

void solve() {
    int n, m; cin >> n >> m;
    vector<int> A(n);
    vector<int> B(m);
    for (int i = 0; i < n; i++) {
        cin >> A[i];
        B[A[i] % m]++;
    }
    if (m == 1) { cout << "1\n"; return; }
    int cnt = (B[0] == 0 ? 0 : 1);
    for (int i = 1; i < m; i++) {
        if (B[i] != 0 && B[m - i] != 0) {
            if (B[i] > B[m - i]) { B[i] -= B[m - i] + 1; B[m - i] = 0; }
            else if (B[i] < B[m - i]) { B[m - i] -= B[i] + 1; B[i] = 0; }
            else { B[i] = 0; B[m - i] = 0; }
            cnt++;
        }
    }
    for (int i = 1; i < m; i++) {
        while (B[i] > 0) {
            B[i]--;
            cnt++;
        }
    }
    cout << cnt << "\n";
}

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

C1. k-LCM (easy version)

It is the easy version of the problem. The only difference is that in this version $𝑘=3$.

You are given a positive integer $𝑛$. Find $𝑘$ positive integers $𝑎_1,𝑎_2,…,𝑎_𝑘$, such that:

• $𝑎_1+𝑎_2+…+𝑎_𝑘=𝑛$
• $𝐿𝐶𝑀(𝑎_1,𝑎_2,…,𝑎_𝑘)≤\frac{𝑛}{2}$

Here $𝐿𝐶𝑀$ is the least common multiple of numbers $𝑎_1,𝑎_2,…,𝑎_𝑘$.

We can show that for given constraints the answer always exists.

Input

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

The only line of each test case contains two integers $𝑛, 𝑘$ $(3≤𝑛≤10^9, 𝑘=3)$.

Output

For each test case print $𝑘$ positive integers $𝑎_1,𝑎_2,…,𝑎_𝑘$, for which all conditions are satisfied.

풀이

규칙을 찾아서 풀었다.

• n이 4의 배수이면 {$\frac{n}{2}, \frac{n}{4}, \frac{n}{4}$} 로 구성할 수 있다.
  
• n이 4의 배수가 아닌 짝수면 {$\frac{n}{2}-1, \frac{n}{2}-1, 2$} 로 구성할 수 있다.
  
• n이 홀수이면 {$\frac{n}{2}, \frac{n}{2}, 1$} 로 구성할 수 있다.

코드

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

void solve() {
    int n, k; cin >> n >> k;
    if (n % 4 == 0) cout << n / 2 << " " << n / 4 << " " << n / 4 << "\n";
    else if (n % 2 == 0) cout << n / 2 - 1 << " " << n / 2 - 1 << " " << 2 << "\n";
    else cout << n / 2 << " " << n / 2 << " " << 1 << "\n";
}

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

C2. k-LCM (hard version)

It is the hard version of the problem. The only difference is that in this version $3≤𝑘≤𝑛$.

You are given a positive integer $𝑛$. Find $𝑘$ positive integers $𝑎_1,𝑎_2,…,𝑎_𝑘$, such that:

• $𝑎_1+𝑎_2+…+𝑎_𝑘=𝑛$
• $𝐿𝐶𝑀(𝑎_1,𝑎_2,…,𝑎_𝑘)≤\frac{𝑛}{2}$

Here $𝐿𝐶𝑀$ is the least common multiple of numbers $𝑎_1,𝑎_2,…,𝑎_𝑘$.

We can show that for given constraints the answer always exists.

Input

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

The only line of each test case contains two integers $𝑛, 𝑘$ $(3≤𝑛≤10^9, 3≤𝑘≤𝑛)$.

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

Output

For each test case print $𝑘$ positive integers $𝑎_1,𝑎_2,…,𝑎_𝑘$, for which all conditions are satisfied.

풀이

위 규칙에서 응용하면 된다.

먼저 k가 3이 될때까지 1을 출력하면서 n과 k를 줄여준다.

이후 위 규칙과 같이 출력하면 된다.

• n이 4의 배수이면 {$\frac{n}{2}, \frac{n}{4}, \frac{n}{4}$} 로 구성할 수 있다.
  
• n이 4의 배수가 아닌 짝수면 {$\frac{n}{2}-1, \frac{n}{2}-1, 2$} 로 구성할 수 있다.
  
• n이 홀수이면 {$\frac{n}{2}, \frac{n}{2}, 1$} 로 구성할 수 있다.

코드

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

void solve() {
    int n, k; cin >> n >> k;
    while (k > 3) {
        n--; k--;
        cout << 1 << " ";
    }
    if (n % 4 == 0) cout << n / 2 << " " << n / 4 << " " << n / 4 << "\n";
    else if (n % 2 == 0) cout << n / 2 - 1 << " " << n / 2 - 1 << " " << 2 << "\n";
    else cout << n / 2 << " " << n / 2 << " " << 1 << "\n";
}

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

https://codeforces.com/contest/1497