Codeforces Global Round 10

찐렌지 2호

 

A - Omkar and Password

Problem - A - Codeforces

\(n\)길이의 배열 \(a\)가 주어진다.

이 배열의 연속된 두 원소 \(a_i, a_{i+1}\)를 골라서, 두 원소의 값이 다르다면 \(a_i, a_{i+1}\)를 삭제하고 그자리에 \(a_i + a_{i+1}\)를 추가하는 연산을 할 수 있다.

 

이 연산을 원하는 만큼 수행했을 때, 결과 배열의 길이의 최소값을 구해야 한다.

 

우선 모든 배열의 값이 같다면, 답은 \(n\)이다.

그렇지 않다면,

배열에서 가장 큰 원소를 하나 골라, 이 원소와 인접한 원소가 현재 원소와 같지 않다면 이 두 원소에 대해 연산하는 것을 반복하자.

그러면 무조건 배열의 길이를 1로 줄일 수 있음을 알 수 있다.

 

#include <bits/stdc++.h>
using namespace std;
 
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
 
ll gcd(ll a, ll b) { for (; b; a %= b, swap(a, b)); return a; }
 
int n;
int a[200001];
 
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
 
    int t; cin >> t;
    while (t--)
    {
        cin >> n;
        for (int i = 0; i < n; i++) cin >> a[i];
 
        bool flag = false;
        for (int i = 0; i < n - 1; i++) if (a[i] != a[i + 1]) flag = true;
 
        if (flag) cout << "1\n";
        else cout << n << '\n';
    }
}

---

B - Omkar and Infinity Clock

Problem - B - Codeforces

\(n\)길이의 배열 \(a\)가 주어진다.

 

이 배열에 다음과 같은 연산을 할 수 있다.

1. 이 배열의 원소의 값 중 최대값을 \(d\)라고 한다.

2. 모든 배열의 원소를 \(d-a_i\)로 교체한다.

 

연산을 \(k\)번 한 후에 배열의 상태를 출력해야 한다.

 

 

관찰을 통해, 연산을 홀수 번 했을 때와 짝수 번 했을 때 2가지 경우로만 나누어짐을 알 수 있다.

2가지 결과를 각각 구한다음 출력하면 된다.

 

#include <bits/stdc++.h>
using namespace std;
 
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
 
ll gcd(ll a, ll b) { for (; b; a %= b, swap(a, b)); return a; }
 
ll n, k;
ll a[200001];
 
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
 
    int t; cin >> t;
    while (t--)
    {
        cin >> n >> k;
        for (int i = 0; i < n; i++) cin >> a[i];
 
        ll mx_val = *max_element(a, a + n);
        ll mn_val = *min_element(a, a + n);
 
        if (k % 2)
        {
            for (int i = 0; i < n; i++) cout << (mx_val - mn_val) - (a[i] - mn_val) << ' ';
            cout << '\n';
        }
        else
        {
            for (int i = 0; i < n; i++) cout << a[i] - mn_val << ' ';
            cout << '\n';
        }
    }
}

---

C - Omkar and Waterslide

Problem - C - Codeforces

\(n\)길이의 배열 \(a\)가 주어진다.

이 배열의 부분 배열을 골라, 부분 배열에 해당하는 모든 원소에 1을 더하는 연산을 할 수 있다.

 

배열을 비내림차순으로 만들기 위해 필요한 연산의 최소 횟수를 구해야 한다.

 

배열의 맨 뒤 부터 살펴보자.

\(a_{i-1} \le a_i\) 라면 연산을 할 필요가 없다.

\(a_{i-1} \gt a_i\) 라면 구간 \([i,n]\)에 대해 \(a_{i-1} - a_i\)번 연산을 하면 된다.

 

#include <bits/stdc++.h>
using namespace std;
 
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
 
ll gcd(ll a, ll b) { for (; b; a %= b, swap(a, b)); return a; }
 
int n;
int a[200001];
 
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
 
    int t; cin >> t;
    while (t--)
    {
        cin >> n ;
        for (int i = 0; i < n; i++) cin >> a[i];
 
        ll ans = 0;
        for (int i = n - 1; i > 0; i--)
        {
            ll d = a[i - 1] - a[i];
            if (d <= 0) continue;
 
            ans += d;
        }
 
        cout << ans << '\n';
    }
}

---

D - Omkar and Bed Wars

Problem - D - Codeforces

\(n\)명의 사람들이 원형으로 서 있다. 이 사람들은 각각 왼쪽 또는 오른쪽 사람을 공격하고 있다.

한 번의 연산으로, 특정한 사람이 공격하는 방향을 바꿀 수 있다.

 

다음 조건을 만족하도록 하기 위해 필요한 연산의 최소값을 구해야 한다.

1. 어떤 사람이 1명으로부터 공격받고 있다면, 그 사람을 공격한다.

2. 0명 또는 2명으로부터 공격받고 있다면, 둘 중 아무나 공격한다.

 

 

관찰을 통해, 공격하는 방향이 같은 사람이 3명 연속으로 있지 않으면, 위의 조건을 만족한다는 사실을 알 수 있다.

같은 방향을 공격하는 연속한 사람들의 개수를 세어, 각각 필요한 연산의 최소 횟수를 구해 더하면 된다.

 

#include <bits/stdc++.h>
using namespace std;
 
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
 
ll gcd(ll a, ll b) { for (; b; a %= b, swap(a, b)); return a; }
 
int n;
string s;
vector <int> v;
 
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
 
    int t; cin >> t;
    while (t--)
    {
        cin >> n;
        cin >> s;
 
        v.clear();
 
        bool flag = false;
        int st = 0;
        for (st; st < n; st++)
        {
            if (s[st] != s[(st + 1) % n])
            {
                flag = true;
                st++;
                break;
            }
        }
 
        if (!flag)
        {
            cout << (n - 1) / 3 + 1 << '\n';
        }
        else
        {
            int cnt = 1;
            for (int i = 0; i < n - 1; i++)
            {
                if (s[(st + i) % n] != s[(st + i + 1) % n])
                {
                    v.push_back(cnt);
                    cnt = 1;
                }
                else cnt++;
            }
            v.push_back(cnt);
 
            int ans = 0;
            for (int x : v)
                ans += x / 3;
            
            cout << ans << '\n';
        }
    }
}

---

E - Omkar and Duck

Problem - E - Codeforces

\(n \times n\)크기의 격자가 있다.

이 격자에 들어갈 수를 원하는대로 정해줄 수 있다.

 

\(q\)개의 쿼리가 들어온다.

각 쿼리에 대해, 격자의 \(1,1\)부터 \(n,n\)까지 최단거리로 이동했을 때 이동 경로에 쓰인 수의 합이 주어진다.

이 합을 보고 원래 이동 경로를 알아내야 한다.

 

 

격자를 다음과 같이 구성하자.

격자의 칸 \(i,j\)에 대해, (0-index)

1. \(j\)가 홀수라면 0을 넣는다.

2. 그렇지 않다면 \(2^{i+j}\)를 넣는다.

 

\(n\)이 4인 경우 격자는 다음과 같다.

 

$$ \left[ 
\begin{matrix} 
1&0&4&0\\ 
2&0&8&0\\ 
4&0&16&0\\ 
8&0&32&0\\
\end{matrix} 
\right] $$

 

그러면 경로상에 있는 총 \(2n-1\)개의 비트로 이루어진 수가 주어지게 된다.

그러면 가장 작은 비트부터 시작해, 다음과 같은 방식으로 경로를 복구할 수 있다.

1. \(i\)번째 비트와 \(i+1\)번째 비트가 같다 : 아래쪽으로 이동

2. \(i\)번째 비트와 \(i+1\)번째 비트가 다르다 : 오른쪽으로 이동

 

#include <bits/stdc++.h>
using namespace std;
 
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
 
ll gcd(ll a, ll b) { for (; b; a %= b, swap(a, b)); return a; }
 
ll n;
ll board[26][26];
 
int main()
{
    cin >> n;
 
    for (int i = 0; i < n; i++) for (int j = 0; j < n; j += 2)
    {
        board[i][j] = (1ll << (i + j));
    }
 
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < n; j++) cout << board[i][j] << ' ';
        cout << endl;
    }
 
    int q; cin >> q;
    while (q--)
    {
        ll k; cin >> k;
        cout << "1 1" << endl;
        int cx = 1, cy = 1;
        int curBit = 1;
        for (int i = 0; i < n * 2 - 2; i++)
        {
            k /= 2;
            if (curBit == k % 2) cout << ++cx << ' ' << cy << endl;
            else cout << cx << ' ' << ++cy << endl;
 
            curBit = k % 2;
        }
    }
}

---

F - Omkar and Landslide

Problem - F - Codeforces

\(n\)미터로 이루어진 산맥 \(h\)가 있다. 산맥의 각 구간의 높이는 \(h_i\)이다.

초기 높이는 오름차순으로 주어진다.

 

이 산맥에 산사태가 일어난다.

산사태가 일어나면, \(h_i + 2 \le h_{i+1}\)를 만족하는 모든 \(i\)에 대해, \(h_{i+1}\)이 1 감소하고 \(h_i\)가 1 증가한다.

산사태는 \(h_i + 2 \le h_{i+1}\)를 만족하는 \(i\)가 존재하지 않을 때까지 반복된다.

 

산사태가 일어난 후에, 산맥의 각 구간의 높이를 알아내야 한다.

 

관찰을 통해, 연속된 세 구간의 높이가 같게 되는 경우는 존재하지 않는다는 사실을 알 수 있다.

또, 산사태가 일어나는 동안 모든 \(i\)에 대해 \(h_i \le h_{i+1}\)를 만족한다는 사실도 알 수 있다.

그러면 산맥의 각 구간의 높이의 합 \(x\)가 주어졌을 때, 산사태가 끝나고 나서 각 구간의 높이로 가능한 경우는 1가지밖에 없다는 사실도 알 수 있다.

 

적당히 \(O(n)\)이나 \(O(n \log n)\)으로 구하면 된다.

 

#include <bits/stdc++.h>
using namespace std;
 
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
 
ll gcd(ll a, ll b) { for (; b; a %= b, swap(a, b)); return a; }
 
int n;
ll h[1000001];
ll ans[1000001];
 
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
 
    //freopen("input.txt", "r", stdin);
 
    cin >> n;
    ll sum = 0;
    for (int i = 0; i < n; i++)
    {
        cin >> h[i];
        sum += h[i];
    }
 
    ll l = 0, r = (ll)1e12 - n + 2;
    while (l + 1 < r)
    {
        ll m = (l + r) / 2;
        ll res;
        if (n % 2 == 0)
            res = (m + m + n - 1) * (n / 2);
        else
            res = (m + m + n - 1) / 2 * n;
        if (res <= sum) l = m;
        else r = m;
    }
 
    for (int i = 0; i < n; i++) ans[i] = l + i;
 
    ll tmp;
    if (n % 2 == 0)
        tmp = (l + l + n - 1) * (n / 2);
    else
        tmp = (l + l + n - 1) / 2 * n;
 
    ll rm = sum - tmp;
 
    for (int i = 0; i < rm; i++) ans[i]++;
 
    for (int i = 0; i < n; i++) cout << ans[i] << ' ';
}

---

G - Omkar and Pies

Problem - G - Codeforces

추가 예정

---

H - ZS Shuffles Cards

Problem - H - Codeforces

추가 예정

---

I - Kevin and Grid

Problem - I - Codeforces

추가 예정