Educational Codeforces Round 99 (Rated for Div. 2) ABCD

import sys
input = sys.stdin.readline
 
for TEST in range(int(input())):
    print(len(input().rstrip()))

 

A - Strange Functions

 

A번에 이렇게 큰 수를 다루는 문제가 나올 리 없기 때문에 당당하게 길이를 출력하였다.

 

 

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
 
ll dp[2000001];
 
int main() {
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
 
    set<int> s;
    for (int i = 1; i <= 2000; ++i) s.insert(i * (i + 1) / 2);
 
    int cur = 1;
    for (int i = 1; i <= 1000000; ++i) {
        dp[i] = cur;
        if (s.find(i + 1) != s.end()) dp[i] += 1;
        if (s.find(i) != s.end()) cur += 1;
    }
 
    int TEST; cin >> TEST; while (TEST--) {
        int n; cin >> n; cout << dp[n] << "\n";
    }
}

 

B - Jumps

 

A₁ = 1, A_i = A_i-1 + i 을 만족하는 수열의 수에 대해 i번 이동하는 것이 최선임이 자명하다.

 

이동 중 뒤로 한 칸 가면, (A_{i-1 :} A_i - 1] 로 갈 수 있음을 관찰을 통해 알 수 있다.

 

마지막 이동에서 뒤로 간 경우 (A_i - 1), A_i 까지 이동한 다음 뒤로 한 칸 이동하는 것이므로 A_{i + 1} 임에 유의한다.

 

 

#include <bits/stdc++.h>
using namespace std;
 
int main() {
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int TEST; cin >> TEST; while (TEST--) {
        int a, b; cin >> a >> b;
        cout << a - 1 << " " << b << "\n";
    }
}

 

C - Ping-pong

 

내 승리 횟수를 최대화하려면 상대가 받아칠 수 없게 체력을 0으로 만들어야 한다.

 

가장 좋은 방법을 내 체력을 아끼는 것이다.

 

따라서 체력이 답이다.

 

 

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<ll, ll> pll;
typedef pair<ld, ld> pld;

int main() {
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);

    int TEST; cin >> TEST; while (TEST--) {
        int n, x; cin >> n >> x;
        vector<int> v; v.push_back(0);
        for (int i = 0; i < n; ++i) {
            int input; cin >> input; v.push_back(input);
        }

        if (n == 1) {
            cout << 0 << "\n"; continue;
        }

        int res = 0;
        for (int i = 1; i < n; ++i) {
            while (v[i] > v[i + 1]) {
                bool flag = false;
                for (int j = i; j >= 1; --j) {
                    if (v[j] > x && x >= v[j - 1] && (j == i || v[j] <= v[i + 1])) {
                        flag = true;
                        res++;
                        int temp = v[j];
                        v[j] = x;
                        x = temp;
                        break;
                    }
                }
                //for (auto xx : v) cout << xx << " "; cout << "\n";
                if (!flag) {
                    break;
                }
            }
        }

        for (int i = 1; i < n; ++i) {
            if (v[i] > v[i + 1]) res = -1;
            if (res == -1) break;
        }

        cout << res << "\n";
    }
}

 

D - Sequence and Swaps

 

코딩의 편의를 위해 수열 첫 자리에 0을 추가하였다.

 

수열의 앞 쪽부터 하나씩 A_i > A_i+1 인지 검사하여, 처음 찾은 i를 j라고 하자.

 

그 다음, 인덱스가 j보다 작은 수 중 A_i+1 ≥ A_j > x > A_j-1 를 만족하는 수를 찾아본다. (i == j 라면 A_i+1 ≥ A_j 는 무시한다.)

 

없다면 더 이상 소트할 수 없는 것이고, 있다면 현재 수와 x를 swap하는 것이 최적이다.

 

정렬이 끝났다면 제대로 정렬되었는지 검사하여 -1을 출력할지 swap 횟수를 출력할지 결정한다.