Educational Codeforces Round 99

A - Strange Functions

Problem - A - Codeforces

\(f(x)\)를 \(x\)를 거꾸로 썼을 때의 값이라고 하자.

\(g(x) = \frac{x}{f(f(x))}\)일 때, \(n\)이 주어지면 \(n\)보다 작거나 같은 정수 중 \(g(x)\)의 함수값이 될 수 있는 수의 개수를 알아내야 한다.

 

\(g(x)\)는 10의 거듭제곱꼴이 될 수 있으므로, 주어지는 수의 자리수를 출력하면 된다.

 

#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--)
    {
        string n; cin >> n;
        cout << n.size() << '\n';
    }
}

---

B - Jumps

Problem - B - Codeforces

수직선 위의 좌표 0에 점이 하나 있다.

현재 점의 위치를 \(y\)라고 했을 때, 다음과 같은 연산을 할 수 있다.

1. 현재 연산이 \(k\)번째 연산이라면, \(y+k\)로 이동한다.

2. \(y-1\)로 이동한다.

 

점을 \(x\)로 이동시키기 위해 필요한 최소 이동 횟수를 구해야 한다.

 

 

원점에서 점을 \(x\)이상의 좌표로 이동시키기 위한 최소 이동 횟수를 \(s\)라고 하자.

관찰을 통해, \(\frac{s(s+1)}{2}-1\)을 제외한 \(\frac{s(s+1)}{2}\) 이하의 점은 \(s\)번 이동하여 이동 가능한 점임을 알 수 있다.

 

#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; }
 
vector <int> vec;
 
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
 
    int sum = 0;
    for (int i = 1; sum <= 1000000; i++)
    {
        sum += i;
        vec.push_back(sum);
    }
 
    int t; cin >> t;
    while (t--)
    {
        int x; cin >> x;
        for (int i = 0; i < vec.size(); i++)
        {
            if (x <= vec[i])
            {
                if (x == vec[i] - 1) cout << i + 2 << '\n';
                else cout << i + 1 << '\n';
                break;
            }
        }
    }
}

---

C - Ping-pong

Problem - C - Codeforces

두 선수가 탁구를 하려고 한다.

선수들은 각각 \(x, y\)의 스태미너를 가지고 있고, 공을 한번 칠 때마다 1의 스태미너를 소모한다.

각 선수는 본인의 차례에 공을 치거나, 일부러 공을 치지 않을 수 있다.

본인이 서브인 경우에는 무조건 공을 쳐야만 하고, 전 판에서 승리한 선수가 서브권을 가진다.

 

각 선수는 자신의 승리수가 최대가 되도록 플레이하고, 그런 방법이 여러가지라면 상대의 승리수가 최소가 되도록 플레이한다.

 

게임이 끝나고 난 후 점수를 알아내야 한다.

 

 

후공이 자신의 승리수가 최대가 되도록 하려면, 선공의 스태미나가 0이 될때까지 아무것도 하지 않으면 된다.

그러면 \(y\)점을 확정적으로 얻을 수 있게 된다.

선공의 맨 마지막 1 스태미나를 사용한 서브는 후공이 받아치는 것이 이득이므로, \(x-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 main()
{
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
 
    int t; cin >> t;
    while (t--)
    {
        int x, y; cin >> x >> y;
        cout << x - 1 << ' ' << y << '\n';
    }
}

---

D - Sequence and Swaps

Problem - D - Codeforces

\(n\)길이의 수열 \(a\)가 주어지고, 정수 \(x\)가 주어진다.

이 수열을 다음과 같은 연산을 이용해 비내림차순으로 만들어야 한다.

 

연산은 다음과 같다.

- \(x\)보다 큰 \(a_i\)를 골라 둘을 swap한다.

 

 

\(n, a_i, x\)의 범위가 모두 500이하이므로, 간단하게 \(O(n^3)\) DP로 풀었다.

 

#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; }
 
const int INF = 987654321;
 
int n, x;
int a[501];
 
int dp[501][501][501];
int solve(int idx, int x, int val)
{
    if (idx == n) return 0;
 
    int& ret = dp[idx][x][val];
    if (ret != -1) return ret;
 
    ret = INF;
    if (a[idx] < val) return ret;
 
    ret = min(ret, solve(idx + 1, x, a[idx]));
    if (a[idx] > x && x >= val)
    {
        int res = solve(idx + 1, a[idx], x) + 1;
        ret = min(ret, res);
    }
 
    return ret;
}
 
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
 
    int t; cin >> t;
    while (t--)
    {
        cin >> n >> x;
 
        for (int i = 0; i <= n; i++)
        {
            for (int j = 0; j <= 500; j++) for (int k = 0; k <= 500; k++)
                dp[i][j][k] = -1;
        }
 
        for (int i = 0; i < n; i++) cin >> a[i];
 
        int ans = solve(0, x, 0);
        if (ans == INF) cout << "-1\n";
        else cout << ans << '\n';
    }
}

---

E - Four Points

Problem - E - Codeforces

좌표평면 위에 4개의 점이 주어진다.

이 4개의 점이 각 변이 축에 평행한 정사각형을 이루도록 이동해야 하고, 한번의 이동으로 점을 각 축 방향으로 1씩 이동할 수 있다.

이 때, 필요한 총 이동의 최소횟수를 구해야 한다.

 

각 점이 어떤 식으로 정사각형을 이루는지 정할 수 있다.

ex) 1-3, 2-4번 점이 각각 x축이 같고, 1-2, 3-4번 점이 각각 y축이 같은 정사각형을 만든다.

 

그러면 각 경우에 점이 이동해야 하는 최소값은 하나의 식으로 정리할 수 있게 되는데, 모든 경우에 대해 이를 구해보면 된다.

 

#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 x[5], y[5];
 
struct Node
{
    int x11, x12, x21, x22;
    int y11, y12, y21, y22;
};
 
Node idx[6] =
{
    {1,2,3,4,1,3,2,4},
    {1,2,3,4,1,4,2,3},
    {1,3,2,4,1,2,3,4},
    {1,3,2,4,1,4,2,3},
    {1,4,2,3,1,2,3,4},
    {1,4,2,3,1,3,2,4}
};
 
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
 
    int t; cin >> t;
    while (t--)
    {
        for (int i = 1; i <= 4; i++)
            cin >> x[i] >> y[i];
 
        ll ans = numeric_limits<ll>::max();
 
        for (int k = 0; k < 6; k++)
        {
            ll res = 0;
 
            ll x11 = x[idx[k].x11], x12 = x[idx[k].x12];
            ll x21 = x[idx[k].x21], x22 = x[idx[k].x22];
 
            if (x11 > x12) swap(x11, x12);
            if (x21 > x22) swap(x21, x22);
 
            ll y11 = y[idx[k].y11], y12 = y[idx[k].y12];
            ll y21 = y[idx[k].y21], y22 = y[idx[k].y22];
 
            if (y11 > y12) swap(y11, y12);
            if (y21 > y22) swap(y21, y22);
 
            res += x12 - x11 + x22 - x21;
            ll xl = max(x11 - x22, x21 - x12);
            ll xr = max(x22 - x11, x12 - x21);
 
            res += y12 - y11 + y22 - y21;
            ll yl = max(y11 - y22, y21 - y12);
            ll yr = max(y22 - y11, y12 - y21);
 
            if (xr < yl)
                res += (yl - xr) * 2;
            if (yr < xl)
                res += (xl - yr) * 2;
 
            ans = min(ans, res);
        }
    
        cout << ans << '\n';
    }
}

---

F - String and Operations

Problem - F - Codeforces

추가 예정

---

G - Forbidden Value

Problem - G - Codeforces

추가 예정