Educational Codeforces Round 100

A - Dungeon

Problem - A - Codeforces

3마리의 몬스터가 있고, 각각의 체력은 \(a,b,c\)이다.

각 턴에 몬스터 중 한마리를 골라 공격해서 체력을 1 감소시킬 수 있다.

단, 각 7번째 공격은 3마리의 체력을 동시에 1 감소시킨다.

 

이 7번째 공격을 이용해 3마리를 동시에 쓰러트릴 수 있는지 여부를 알아내야 한다.

 

먼저 7번의 공격의 공격력의 합은 9이므로, \(a+b+c\)가 9로 나누어 떨어지는지,

그리고 셋 중 가장 작은 값이 \(\frac{(a+b+c)}{9}\) 보다 크거나 같은지 확인하면 된다.

 

#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 main()
{
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
 
    int t; cin >> t;
    while(t--)
    {
        int a, b, c; cin >> a >> b >> c;
 
        bool ans = true;
        if ((a + b + c) % 9) ans = false;
        else
        {
            if (min(a, (min(b, c))) < (a + b + c) / 9) ans = false;
        }
 
        if (ans) cout << "YES\n";
        else cout << "NO\n";
    }
}

---

B - Find The Array

Problem - B - Codeforces

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

 

새로운 \(n\)길이의 배열 \(b\)를 만들어야 하는데, 다음과 같은 조건을 만족해야 한다.

1. \(b\)의 각 원소는 \(10^9\)이하의 자연수이다.

2. 각 \(b_i\)에 대하여, \(b_i\)가 \(b_{i+1}\)의 약수이거나, \(b_{i+1}\)가 \(b_i\)의 약수여야 한다.

3. \(a\)의 모든 원소의 합이 \(S\)라고 했을 때, \(|a_i-b_i|\)의 합이 \(S\)의 절반 이하여야 한다.

 

 

\(a\)의 홀수번째 인덱스와 짝수번째 인덱스의 합을 각각 구하자.

둘 중 작은 쪽을 전부 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;
ll a[51];
 
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
 
    int t; cin >> t;
    while (t--)
    {
        cin >> n;
 
        ll sum[2] = { 0,0 };
        for (int i = 0; i < n; i++)
        {
            cin >> a[i];
            sum[i % 2] += a[i];
        }
 
        for (int i = 0; i < n; i++)
        {
            if ((sum[0] < sum[1]) == (i % 2 == 0)) cout << "1 ";
            else cout << a[i] << ' ';
        }
        cout << '\n';
    }
}

---

C - Busy Robot

Problem - C - Codeforces

수직선 상에 로봇이 서 있고, 0초에 좌표 0에 서있다.

이 로봇에 \(n\)개의 명령을 내리려고 한다.

각 명령은 \(t_i\)시간에 \(x_i\) 위치로 이동하라는 명령이다.

 

\(t_i\)시간에 로봇이 움직이고 있지 않다면, 현재 위치에서 \(x_i\)로 1초에 1의 속도로 이동한다.

움직이고 있다면, 그 명령은 무시된다.

 

어떤 \(i\)번째 명령에 대해, \(t_i\)와 \(t_{i+1}\)시간 사이에 \(x_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;
ll t[100001];
ll x[100001];
 
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 >> t[i] >> x[i];
        t[n] = 1e18;
 
        ll cx = 0;
 
        ll last = 0;
        int ans = 0;
 
        int a = 0, b = 0;
 
        for (int i = 0; i < n; i++)
        {
            if (last <= t[i])
            {
                last = t[i];
 
                if (cx < x[i])
                {
                    a = 1;
                    b = cx - t[i];
                    last += x[i] - cx;
                }
                else if (cx > x[i])
                {
                    a = -1;
                    b = cx + t[i];
                    last += cx - x[i];
                }
                else
                {
                    a = 0;
                    b = cx;
                }
 
                cx = x[i];
                if (t[i + 1] >= last) ans++;
            }
            else
            {
                ll l = a * t[i] + b;
                ll r = a * min(last, t[i + 1]) + b;
 
                if (l > r) swap(l, r);
                if (l <= x[i] && x[i] <= r) ans++;
            }
        }
 
        //cout << "ANS:";
        cout << ans << '\n';
    }
}

---

D - Pairs

Problem - D - Codeforces

\(2n\)개의 수가 있다. 이 수 들을 \(n\)개의 쌍으로 묶으려고 한다.

각 쌍에서 \(x\)개를 골라 둘 중 최소값을, 남은 \(n-x\)개의 쌍에서는 둘 중 최대값을 골라 집합 \(b\)를 만든다고 하자.

 

\(b\)가 주어졌을 때, 가능한 \(x\)의 개수를 알아내야 한다.

 

 

먼저, \(x\)의 최소값과 최대값을 알면 그 사이에 있는 값도 모두 \(x\)가 될 수 있음을 관찰로써 알 수 있다.

최소값과 최대값은 set등을 이용해 그리디하게 구해주면 된다.

 

#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 b[200001];
 
set <int> st;
set <int> tmp;
 
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
 
    int T; cin >> T;
    while (T--)
    {
        cin >> n;
        st.clear();
 
        int last = 1;
 
        for (int i = 0; i < n; i++)
        {
            cin >> b[i];
            if (last < b[i])
            {
                for (int j = last; j < b[i]; j++) st.insert(j);
            }
 
            last = b[i] + 1;
        }
 
        while (last <= 2 * n)
        {
            st.insert(last);
            last++;
        }
 
        int mn = 0, mx = 0;
 
        tmp = st;
        for (int i = 0; i < n; i++)
        {
            auto it = tmp.lower_bound(b[i]);
            if (it != tmp.end())
            {
                mx++;
                tmp.erase(it);
            }
        }
 
        tmp = st;
        for (int i = n - 1; i >= 0; i--)
        {
            auto it = tmp.lower_bound(b[i]);
            if (it == tmp.begin()) mn++;
            else
            {
                --it;
                tmp.erase(it);
            }
        }
 
        cout << mx - mn + 1 << '\n';
    }
}

---

E - Plan of Lectures

Problem - E - Codeforces

\(n\)개의 강의가 있다.

1개를 제외한 모든 강의에는 선수 강의가 있어서, 그 강의를 듣기 전에는 수강이 불가능하다.

또 \(k\)개의 특별한 강의 쌍 \((x, y)\)이 있는데, \(x\)를 듣고 난 바로 다음 \(y\)를 들어야 함을 뜻한다.

 

위의 조건을 만족하도록 모든 강의를 듣는 방법이 존재하는지 여부를 알아내고, 존재한다면 그 중 아무거나 하나를 출력해야 한다.

 

먼저 \(k\)개의 강의 쌍에 의해 무조건 연속으로 들어야 하는 강의들을 하나로 압축해주자.

이 압축한 강의들에 대해 위상정렬을 만들면 된다. 위상정렬이 존재하지 않으면 불가능한 경우이다.

 

#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, k;
int p[300001];
 
int rc[300001];
int rp[300001];
 
set <int> graph[300001];
vector <vector <int> > grp;
int grp_num[300001];
int grp_idx[300001];
 
int in[300001];
 
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
 
    cin >> n >> k;
    for (int i = 1; i <= n; i++) cin >> p[i];
    for (int i = 0; i < k; i++)
    {
        int x, y; cin >> x >> y;
        if (rc[x] || rp[y])
        {
            cout << 0;
            return 0;
        }
 
        rc[x] = y;
        rp[y] = x;
    }
 
    for (int i = 1; i <= n; i++)
    {
        if (rp[i]) continue;
 
        vector <int> cg;
 
        int idx = 0;
        int ci = i;
        while (rc[ci])
        {
            cg.push_back(ci);
            grp_num[ci] = grp.size();
            grp_idx[ci] = idx++;
            ci = rc[ci];
        }
 
        cg.push_back(ci);
        grp_num[ci] = grp.size();
        grp_idx[ci] = idx;
 
        grp.push_back(cg);
    }
 
    for (int i = 1; i <= n; i++)
    {
        if (p[i] == 0) continue;
        int pg = grp_num[p[i]];
        int cg = grp_num[i];
 
        if (pg != cg)
        {
            if (graph[pg].find(cg) != graph[pg].end()) continue;
 
            graph[pg].insert(cg);
            in[cg]++;
        }
        else
        {
            if (grp_idx[p[i]] > grp_idx[i])
            {
                cout << 0;
                return 0;
            }
        }
    }
 
    vector <int> ans;
    queue <int> q;
    for (int i = 0; i < grp.size(); i++)
    {
        if (in[i] == 0) q.push(i);
    }
 
    while (!q.empty())
    {
        int cg = q.front(); q.pop();
        for (auto v : grp[cg]) ans.push_back(v);
        for (auto ng : graph[cg])
        {
            if (--in[ng] == 0) q.push(ng);
        }
    }
 
    if (ans.size() != n)
    {
        cout << 0;
        return 0;
    }
 
    for (auto v : ans) cout << v << ' ';
}

---

F - Max Correct Set

Problem - F - Codeforces

추가 예정