Algorithm/코드포스

Educational Codeforces Round 124 (Rated for Div. 2) 1545 -> 1507

Edyy 2022. 3. 12. 12:59

https://codeforces.com/contest/1651

 

Dashboard - Educational Codeforces Round 124 (Rated for Div. 2) - Codeforces

 

codeforces.com

 

!!!! 모든 답은 제 풀이일 뿐 정해가 아닐 수 있습니다 !!!!

 

A. Playoff

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

 

Problem - A - Codeforces

 

codeforces.com

 

문제

 

n이 주어진다. 2^n명이 토너먼트에 참가하는데 처음에는 1vs2 , 3vs4 와 같은 바로 옆사람과 대결한다. 그리고 대결하는 각 사람의 인덱스를 더했을때 짝수면 숫자가 큰사람이 이기고 홀수면 숫자가 작은사람이 이긴다. n이 주어졌을 때 최종적으로 승리하는 사람을 출력하는 문제

 

풀이

 

첫경기는 무조건 홀수가 나오니 앞 인덱스가 이기고 이들은 모두 홀수 인덱스다. 그럼 이제 앞으로 더해질 경기들은 다 짝수이니 무조건 뒷사람이 이기고 결론은 2^n -1번째 사람이 우승한다.

 

코드

 

    #include <bits/stdc++.h>
    using namespace std;
     
    int main() {
        ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
        int T;
        cin >> T;
        while (T--) {
            long long n;
            cin >> n;
            cout << (1LL << n) - 1 << '\n';
        }
     
    }

 

B. Prove Him Wrong

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

 

Problem - B - Codeforces

 

codeforces.com

문제

 

n이 주어진다. 인덱스가 서로다른 i,j를 선택하여 a[i] = a[j] = abs(a[i]-a[j])로 바꾸는 연산을 딱 한번 했을때 어떤 인덱스를 선택하더라도 주어진 배열의 총합이 적어지지 않는 배열(단 원소의 크기는 1<= a[i] <= 10^9)을 만들 수 있으면 YES와 그러한 배열을 출력하고 그렇지 않으면 NO를 출력한다

 

풀이

 

n이 주어졌을때 만들 수 있는 최소 숫자들로 구성된 숫자는 a[1]이 1이고 이후부터 3을 곱하는 배열이다. 원소중 하나라도 10^9를 넘어간다면 NO를 출력하고 이외에는 YES와 3을 곱해서 출력하면 된다.

 

코드

 

    #include <bits/stdc++.h>
    using namespace std;
    long long a[1001];
    const long long MAX = 1000000000;
    int main() {
        ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
        int T;
        cin >> T;
        while (T--) {
            int n;
            cin >> n;
            bool flag = true;
            a[1] = 1;
            for (int i = 2; i <= n; i++) {
                a[i] = a[i - 1] * 3LL;
                if (a[i] > MAX) {
                    flag = false;
                    break;
                }
            }
            if (flag) {
                cout << "YES\n";
                for (int i = 1; i <= n; i++)cout << a[i] << ' ';
                cout << '\n';
            }
            else {
                cout << "NO\n";
            }
        }
     
    }

 

자세한 설명에 중점을 두기보다는 대회 기록에 중점을 둔 글입니다 !

틀린 부분은 감사히 지적받겠습니다.