Codeforces Round #761 (Div. 2) 1476 -> 1522

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

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

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

 

 

A. Forbidden Subsequence

Problem - A - Codeforces

Problem - A - Codeforces

문제

 

두 개의 문자열 S와 T가 주어졌을 때, 문자열 S에 있는 알파벳을 그대로 사용하되, 부분 문자열에 T가 없는 사전적으로 가장 작은 새로운 문자열을 출력하는 문제 단 T는 a,b,c가 각 1번씩 등장하는 문자열이다

 

풀이

 

T가 abc만 아니면 S를 정렬해서 그대로 출력하고 abc면 , 정렬 후 b와 c의 위치만 바꿔준 후 출력한다.

 

 

코드

 

#include <bits/stdc++.h>
using namespace std;
string s, t;
int cnt[130];
int main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    int T;
    cin >> T;
    while (T--) {
        cin >> s >> t;
        sort(s.begin(), s.end());
        for (int i = 'a'; i <= 'z'; i++)cnt[i] = 0;
        for (int i = 0; i < s.size(); i++) {
            cnt[s[i]]++;
        }
        if (t == "abc") {
            if (cnt['a'] && cnt['b'] && cnt['c']) {
                for (int i = 0; i < s.size(); i++) {
                    if (s[i] == 'c') {
                        for (int j = 0; j < i; j++) {
                            if (s[j] == 'b') {
                                swap(s[i], s[j]);
                                break;
                            }
                        }
                    }
                }
                cout << s << '\n';
            }
            else {
                cout << s << '\n';
            }
        }
        else cout << s << '\n';
    }
}

 

 

B.   GCD Problem

Problem - B - Codeforces

Problem - B - Codeforces

 

문제

 

n이 주어질때 a+b+c = n이고 gcd(a,b) = c인 서로 다른 양수를 출력하는 문제

 

풀이

 

n 이 짝수라면 (n-1)/2 , (n-1)/2+1, 1 을 출력해주면 되고 , n이 홀수라면 n/2 +- 2 범위에서 서로 홀수가 되게 출력한 후 1을 출력해주면 된다.

 

코드

 

#include <bits/stdc++.h>
using namespace std;
string s, t;
int cnt[130];
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;
        if (n % 2) {
            long long n2 = n / 2;
            if (n2 % 2)cout << n2 + 2 << ' ' << n2 - 2 <<' ' << 1 << '\n';
            else cout << n2 + 1 << ' ' << n2 - 1 << ' ' << 1 << '\n';
        }
        else {
            cout << (n-1) / 2 << ' ' << (n-1) / 2 + 1 << ' ' << 1 << '\n';
        }
    }
}

C.   Paprika and Permutation

Problem - C - Codeforces

Problem - C - Codeforces

 

문제

 

길이가 n인 배열이 주어진다. 이때 인덱스 하나와 x를 골라 a[i]%=x를 하는 연산을 할 수 있을때 주어진 배열을 permutation으로 만들 최소 연산의 수를 출력하는 문제 ,단 만들 수 없다면 -1을 출력

 

풀이

 

1~n까지의 원소가 하나라도 있으면 그걸 쓰고, 나머지는 i*2+1 수중에 가장 작은 값을 골라 채워준다. 이때 채울 원소가 없으면 답은 -1

 

코드

 

#include <bits/stdc++.h>
using namespace std;
multiset<int> Set;
bool check[100001];
int main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    int T;
    cin >> T;
    while (T--) {
        Set.clear();
        int n;
        cin >> n;
        for (int i = 1; i <= n; i++) {
            check[i] = false;
        }
        for (int i = 1; i <= n; i++) {
            int t;
            cin >> t;
            if (t >= 1 && t <= n) {
                if (check[t] == false) {
                    check[t] = true;
                    continue;
                }
            }
            Set.insert(t);
        }
        int cnt = 0;
        for (int i = 1; i <= n; i++) {
            if (check[i])continue;
            auto it = Set.lower_bound(i);
            if (it == Set.end()) {
                cnt = -1;
                break;
            }
            if (*it == i) {
                Set.erase(it);
                continue;
            }
            int i2 = i * 2 + 1;
            it = Set.lower_bound(i2);
            if (it == Set.end()) {
                cnt = -1;
                break;
            }
            cnt++;
            Set.erase(it);
        }
        cout << cnt << '\n';
    }
}

 

 

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

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