Codeforces Round #747 (Div. 2) , 1551 -> 1529 (-22)

Dashboard - Codeforces Round #747 (Div. 2) - Codeforces

Dashboard - Codeforces Round #747 (Div. 2) - Codeforces

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

 

A. Consecutive Sum Riddle

Problem - A - Codeforces

Problem - A - Codeforces

문제

 

n이 주어졌을 때 ,l ~ r 구간의 합이 n인 값 l , r 을 출력하는 문제

 

풀이

 

l을 -(n-1) 로 , r을 n으로 두면 합이 n이 된다. 

코드

 

#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 << -(n - 1) << ' ' << n << '\n';
    }
}

B. Special Numbers

Problem - B - Codeforces

Problem - B - Codeforces

문제

n과 k가 입력으로 주어진다.

n의 서로다른 제곱수의 합으로 모든 숫자들을 나타냈을때 k번째 수를 출력하는 문제

 

풀이

 

k를 2진수로 바꾼뒤, 10진수로 바꿀때는 n진법을 쓰면 된다.

 

코드

 

#include <bits/stdc++.h>
using namespace std;
const long long mod = 1000000007;
int main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    int T;
    cin >> T;
    while (T--) {
        long long n, k;
        cin >> n >> k;
        vector<long long> v;
        while (k) {
            if (k % 2)v.push_back(1);
            else v.push_back(0);
            k /= 2;
        }
        long long ans = 0, start = 1;
        for (long long kk : v) {
            ans = (ans + kk * start)%mod;
            start *= n;
            start %= mod;
        }
        cout << ans << '\n';
    }
}

C. Make Them Equal

Problem - C - Codeforces

Problem - C - Codeforces

문제

문자열이 주어질때 문자열의 모든 문자를 주어진 입력 c로 바꾸어야 한다. 이 때 1~n까지 임의의 숫자 x를 지정해서, 
x로 나누어 지지 않는 모든 인덱스를 c로 바꾼다. 이때 최소 연산의 횟수

 

풀이

 

c가 아닌 모든 인덱스의 약수를 구해서 따로 check해주고, 1 ~ n까지의 범위중 check가 안된 수가 1개라도 있으면 1과 그 수를 출력 해주면 되고, 아니라면 2와 n,n-1을 출력 해주면 된다. 이때 시작부터 모두 같으면 답은 0을 출력해준다.

 

코드

 

#include <bits/stdc++.h>
using namespace std;
bool check[300001];
int main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    int T;
    cin >> T;
    while (T--) {
        int n; char c1;
        cin >> n >> c1;
        for (int i = 1; i <= n; i++)check[i] = false;
        string s;
        cin >> s;
        s = " " + s;
        bool flag = true;
        check[1] = true;
        for (int i = 1; i <= n; i++) {
            if (s[i] != c1) {
                flag = false;
                check[i] = true;
                int temp = i;
                int j2 = sqrt(temp);
                for (int j = 2; j <= j2; j++) {
                    if (temp % j == 0) {
                        check[j] = check[temp / j] = true;
                    }
                }
            }
        }
        if (flag) {
            cout << 0 << '\n';
            continue;
        }
        int tcnt = 0,ans=-1;
        for (int i = 2; i <= n; i++) {
            if (check[i] == false) {
                tcnt++;
                ans = i;
            }
        }
        if (tcnt == 0) {
            cout << 2 << '\n'<< n-1<<' '<<n<<'\n';
        }
        else {
            cout << 1 << '\n' << ans << '\n';
        }
    }
}

E1. Rubik's Cube Coloring (easy version)

Problem - E1 - Codeforces

Problem - E1 - Codeforces

문제

 

포화 이진 트리가 주어졌을 때, 각 노드마다 색칠을 한다. 0 ~ 5까지 색칠하지만 0과 1, 2 와 3, 4 와 5 의색끼리는 서로 인접하면 안된다. 이때 높이가 k층인 포화 이진트리를 모두 색칠하는 경우의 수를 출력하는 문제

 

풀이

 

노드가 아래에서 생성될수록 노드 갯수만큼 4를 곱해주면 된다. 이때 미리 2의 제곱수를 구해놓고 , 제곱을 로그로 하는 함수를 구현하여 푼다.

 

코드

 

#include <bits/stdc++.h>
using namespace std;
long long d[61],pow2[61],ans[61];
const long long mod = 1000000007;
long long mul(long long x, long long y) {
    long long ans = 1;
    while (y) {
        if (y % 2) {
            ans *= x;
            ans %= mod;
        }
        x *= x;
        x %= mod;
        y /= 2;
    }
    return ans;
}
int main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    pow2[0] = 1;
    for (int i = 1; i < 61; i++) {
        pow2[i] = pow2[i - 1] * 2LL;
    }
    d[1] = 6;
    for (int i = 2; i <= 60; i++) {
        d[i] = (d[i - 1] * mul(4,pow2[i-1])) % mod;
    }
    int n;
    cin >> n;
    cout << d[n]<< '\n';
}

레이팅 변화 : 

1551 -> 1529 (-22)

 

 

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

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