Educational Codeforces Round 84 (Rated for Div. 2)

20/03/23실시한 코포

역대급으로 조졌다... ㅎ 

https://codeforces.com/contest/1327/problem/A

Problem - A - Codeforces

t개의 테스트 케이스 동안 n과 k를 입력 받는다. 각 케이스 마다 n을 k개의 다른 홀수들의 합으로 나타 낼 수 있는지를 묻는다.

홀수를 홀수 번 더하면 무조건 홀수이고 짝수번 더하면 무조건 짝수이다. 

그 외 경우 n과 k가 모두 홀수 일경우 k개의 다른 홀수들의 최소는 1,3,5,,.. ,k,..2k-1이다. 이수들의 합은 k*k이고 

n과 k가 모두 짝수 일 경우 k개의 다른 홀수들은 1,3,5,7, ... k-1,k+1,.... 2k-1이고 이수들의 합또한 k*k 이다.

k의 범위때문에 k*k를 고려해 k를 longlong으로 설정해줘야한다.

 
    int T;
    cin >> T;
    while (T--) {
        ll a, b;
        cin >> a >> b;
        if (a % 2 == 0 && b % 2) { 
            cout << "NO";
        }
        else if (a % 2 == 1 && b % 2 == 0) {
            cout << "NO";
        }
        else {
            if (a < b * b)
                cout << "NO";
            else
                cout << "YES";
        }
        cout << "\n";
    }
 

https://codeforces.com/contest/1327/problem/B

Problem - B - Codeforces

문제는 길지만 간단히 하면 1~n까지 공주와 왕자가 있다.  입력으로는 공주마다 원하는 왕자들을 주고 위 공주부터 한명씩 자신이 원하는 왕자들중 선택되지 않은 왕자를 선택한다. 이렇게 선택할 수 있는 번호 증가순대로 하고 딱 한번 선택되지 않은 공주와 왕자를 이어주려고 한다. 이렇게 이었을떄 선택된 쌍의 수가 증가하면 IMPROVE를 출력하고 그 공주와 왕자의 번호를 출력한다. 이렇게 쌍이 증가하는 경우가 존재 하지 않는다면 OPTIMAL을 출력한다.

공주번호대로 연결되는 쌍이 있으면 왕자와 이어준다. 이렇게 쭉 이어주고 선택되지 않은 공주와 왕자가 존재한다면 둘을 이어주면되고 존재하지 않는다면 IMPROVE이다 만약 그 둘이 이미 이어져 있었다면 위의 선택때 둘은 선택 되었어야한다.

const int MAXN = 100005;
int arr[MAXN];
int brr[MAXN];
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    int T;
    cin >> T;
    while (T--) {
        int n;
        cin >> n;
        for (int i = 1; i <= n; i++) {
            brr[i] = 0;
            arr[i] = 0;
        }
        for (int i = 1; i <= n; i++) {
            int m;
            cin >> m;
            int che = 0;
            for (int j = 1; j <= m; j++) {
                int tem;
                cin >> tem;
                if (che == 0 && brr[tem] == 0) {
                    che = 1;
                    brr[tem] = i;
                    arr[i] = tem;
                }
            }
        }
        int a = -1, b = -1;
        for (int i = 1; i <= n; i++) {
            if (arr[i] == 0&& a==-1)
                a = i;
            if (brr[i] == 0&& b==-1)
                b = i;
        }
        if (a == -1 || b == -1)
            cout << "OPTIMAL";
        else {
            cout << "IMPROVE\n";
            cout << a << ' ' << b;
        }
        cout << "\n";
    }
}
 
 

https://codeforces.com/contest/1327/problem/C

Problem - C - Codeforces

이거도 사실 굉장히 쉬운문제이다. 이 풀이를 생각했지만 문제를 후루룩 대충 읽다가 at least once를 최소로 해석하고 최소n을 출력하라는건줄 알고 쌩 고생한 문제

 n,m,k(높이,가로,칩갯수)가 주어지고 k개의 줄에 칩의 위치 k개의 줄에 칩의 목적지가 주어진다. 여기서 칩들 전체를 동시에 상하 좌우로 움직일수 있고 맵밖으로 나가게 될 경우 제자리에서 움직이지 않는다. 또한 칩들은 겹쳐진다. 각 칩들이 목적지 까지 최소한 한번은 도달 하여야 한다. 이렇게 하기위한 상하좌우 움직임을 표시하라 

라는 문제이다. 움직이는 횟수가 2*n*m을 초과하면 안된다.

칩이 겹쳐지기 때문에  n-1번 위로 하고 m-1번 왼쪽으로 하면 모든칩이 (1,1)에 뭉쳐진다. 그리고 ㄹ자로 모든 칸을 훑으면 (n - 1) + (m - 1) + n * m - 1안에 모든 칸을 볼 수 있다.

int n, m, k;
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
 
    cin >> n >> m >> k;
    int x, y;
    for (int i = 0; i < k; i++) cin >> x >> y;
    for (int i = 0; i < k; i++) cin >> x >> y;
    int ans = (n - 1) + (m - 1) + n * m - 1;
    cout << ans << '\n';
    for (int i = 0; i < n - 1; i++)
        cout << "U";
    for (int i = 0; i < m - 1; i++)
        cout << "L";
    for (int i = 0; i < n; i++)    {
        for (int j = 0; j < m - 1; j++)    {
            if (i % 2 == 0) cout << "R";
            else cout << "L";
        }
        if (i != n - 1) cout << "D";
    }
}

https://codeforces.com/contest/1327/problem/D

Problem - D - Codeforces

up solving할때도 풀지 못했다... 다른 사람 코드를 봐도 잘 이해가 안간ㄷ.....

 

 

https://codeforces.com/contest/1327/problem/E

Problem - E - Codeforces

div 2인데 2000명 가까이 푼 문제이다. 

입력으로 n을 입력 받는다.(1<=n<=2*10^5) 0부터 10^n - 1까지 숫자들을 보면서 블럭이 몇개인지 찾아 야 힌다.

n이 5개인 경우 

1크기 블럭 과 나머지들 ㅁㅇㅇㅇㅇ(ㅇ이 나머지들) ㅇㅁㅇㅇㅇ, ㅇㅇㅁㅇㅇ, ㅇㅇㅇㅁㅇ,ㅇㅇㅇㅇㅁ이렇게 5개가 나온다. 1크기 블럭이 되기위해선 ㅁ과 붙어 있는 ㅇ은 ㅁ과 숫자가 달라야 함으로 ㅁㅇㅇㅇㅇ의 경우 ㅇㅇㅇㅇ의 경우의 수는 9*10*10*10 이다.

ㅇㅁㅇㅇㅇ, ㅇㅇㅁㅇㅇ, ㅇㅇㅇㅁㅇ의경우 ㅁ의 앞과 뒤 모두가 ㅁ과 달라야 함으로 9*9*10*10 이다.

ㅇㅇㅇㅇㅁ이와 같은 경우도 9*10*10*10이다.

2크기 블럭의 경우 ㅁㅁㅇㅇㅇ ,ㅇㅁㅁㅇㅇ,ㅇㅇㅁㅁㅇ,ㅇㅇㅇㅁㅁ이고 9*10*10 , 9*9*10, 9*9*10, 10*10*9이런식으로 된다. MOD는 알아서 해줘야한다!

ll arr[MAXN];
 
int n;
 
 
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    cin >> n;
    arr[0] = 1;
    for (int i = 1; i <= n; i++) {
        arr[i] = arr[i - 1] * 10 % MOD;
    }
    for (int i = 1; i < n; i++) {
        ll tem = 2 * 9 * arr[n - 1 - i]%MOD;
        if (i < n - 1) {
            tem += (n-i-1)*81 * arr[n - 2 - i] % MOD;
        }
        tem = tem * 10 % MOD;
        cout << tem << ' ';
    }
    cout << 10;
}

여기까지!