Codeforces Educational #82

A. Erasing Zeroes

Problem - A - Codeforces

Problem - A - Codeforces

길이 \(n\)의 binary string \(s\)가 주어진다.

\(1\)과 \(1\) 사이에 존재하는 \(0\)의 개수를 세는 문제이다.

#include <bits/stdc++.h>
using namespace std;
 
int main(void) {
    int t; cin >> t;
    while (t--) {
        string s; cin >> s;
        int cnt = 0;
        int prv = -1;
        for (int i = 0; i < s.size(); i++) {
            if (s[i] == '1') {
                cnt += (prv == -1 ? 0 : i - prv - 1);
                prv = i;
            }
        }
        cout << cnt << '\n';
    }
    return 0;
}

 

 

B. National Project

Problem - B - Codeforces

Problem - B - Codeforces

길이 \(n\)의 도로를 수리해야 한다.

해당 지방은 날씨가 좋은 \(g\)일과 날씨가 나쁜 \(b\)일이 번갈아가며 나타나는데 (\(g, b, g, b, \dots\))

날씨가 좋은 날 수리한 구간은 퀄리티가 좋고, 날씨가 나쁜 날 수리한 구간은 퀄리티가 나쁘다.

날마다 도로를 한 unit만큼 수리할지, 그냥 쉴지 선택할 수 있다.

전체 도로의 절반 이상이 퀄리티 좋은 상태로 수리가 끝나려면 최소 며칠이 필요한지 구해야 한다.

 

반드시 퀄리티 좋아야 하는 구간의 길이 \(h = \frac{n+1}{2}\)

 

\(q = h / g\), \(r = h\% g\), \(f = \begin{cases}1  & \text{if $r = 0$} \\ 0  & \text{else}\end{cases}\)일 때

날씨 좋은 날이 \(h\)일이 되는 데 필요한 최소 일수 \(k = h + b * (q - f)\)

 

답은 \(\max(n, k)\)이다.

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
 
int main(void) {
    int t; cin >> t;
    while (t--) {
        ll n, g, b;
        cin >> n >> g >> b;
        ll h = (n + 1) / 2;
        ll q = h / g;
        ll r = h % g;
        ll cnt = h + b * max(0ll, (r ? q : q-1));
        cout << max(n, cnt) << '\n';
    }
    return 0;
}

 

 

C. Perfect Keyboard

키보드는 \(26\)개의 소문자 알파벳 한 줄로 구성된다.

패스워드가 문자열 \(s\)로 주어지는데,

\(s\) 안에서 이웃한 문자들은 키보드에서도 이웃해야 한다.

위 조건을 만족하는 키보드 조합을 구하는 문제이다.

 

그래프로 모델링하여 생각할 수 있다.

 

키보드 구성이 불가능한 케이스

1) 어떤 정점에 연결된 간선이 3개 이상인 경우

2) 사이클이 존재하는 경우

 

#include <bits/stdc++.h>
using namespace std;
 
vector<bool> visited(26);
vector<set<int> > adj;
 
bool dfs1(int u, int p) {
    bool ret = false;
    visited[u] = true;
    for (int v: adj[u]) {
        if (v == p) continue;
        if (!visited[v]) ret = ret || dfs1(v, u);
        else return true;
    }
    return ret;
}
 
void dfs2(int u) {
    cout << (char)('a'+u);
    visited[u] = true;
    for (int v: adj[u]) {
        if (!visited[v]) {
            dfs2(v);
        }
    }
}
 
int main(void) {
    int t; cin >> t;
    while (t--) {
        string s; cin >> s;
        adj.clear(); adj.resize(26);
        for (int i = 1; i < s.size(); i++) {
            int a = s[i-1] - 'a';
            int b = s[i] - 'a';
            adj[a].insert(b);
            adj[b].insert(a);
        }
        
        bool flag = false;
        visited.assign(26, false);
        for (int i = 0; i < 26; i++) {
            if (!visited[i]) {
                flag = dfs1(i, i);
                if (flag) break;
            }
            if (adj[i].size() >= 3) {
                flag = true;
                break;
            }
        }
        if (flag) {
            cout << "NO\n";
        }
        else {
            cout << "YES\n";
            visited.assign(26, false);
            for (int i = 0; i < 26; i++) {
                if (!visited[i] && adj[i].size() == 1) dfs2(i);
            }
            for (int i = 0; i < 26; i++) {
                if (!visited[i]) cout << (char)('a'+i);
            }
            cout << '\n';
        }
    }
    return 0;
}

 

 

D. Fill The Bag

Problem - D - Codeforces

Problem - D - Codeforces

사이즈가 \(n\)인 가방 하나와 \(m\)개의 박스가 주어진다.

박스의 사이즈는 모두 \(2\)의 거듭제곱 꼴이다.

\(2^p\) 사이즈의 박스 하나를 \(2^{p-1}\) 사이즈의 박스 2개로 나눌 수 있다.

가방을 박스로 빈틈없이 채울 때 필요한 최소 division 횟수를 구하는 문제이다.

 

우선 박스들의 크기 합이 \(n\) 이상이면 가방을 채울 수 있다.

모든 박스를 크기 \(1\)의 박스로 만들 수 있기 때문이다.

 

binary representation of \(n\)의 낮은 비트부터 채우자.

1) \(i\)번째 비트가 0인 경우

\(2^i\) 사이즈 박스가 필요 없음을 알 수 있다.

남은 \(2^i\) 사이즈 박스들은 \(2^{i+1}\) 사이즈 박스로 만든다.

 

2) \(i\)번째 비트가 1인 경우 & \(2^i\) 사이즈 박스가 있는 경우

\(2^i\) 사이즈 박스 하나를 사용한다.

남은 \(2^i\) 사이즈 박스들은 \(2^{i+1}\) 사이즈 박스로 만든다.

 

3) \(i\)번째 비트가 1인 경우 & \(2^i\) 사이즈 박스가 없는 경우

남은 박스들 중 가장 작은 박스의 사이즈를 \(2^k\)라고 하자.

해당 박스를 쪼개서 \(2^i\) 사이즈 박스를 만들어야 한다.

이때 필요한 division 횟수는 \(k-i\)이다.

이 과정에서 만들어지는 박스들을 통해 \(n\)의 \(i \le x \le k-1\)번째 비트들을 채울 수 있다.

ex) \(10000\) -> \(1111\)

이후 \(n\)의 \(k\)번째 비트부터 다시 시작한다.

\(2^{k-1}\) 사이즈 이하의 박스들을 모두 합쳐도 \(2^k\) 사이즈 박스를 만들 수 없기 때문이다.

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
 
int log2(ll a) {
    int ret = 0;
    while (a > 1) {
        ret++;
        a /= 2;
    }
    return ret;
}
 
int main(void) {
    int t; cin >> t;
    while (t--) {
        ll n, m, sum = 0;
        cin >> n >> m;
        vector<int> box(65);
        while (m--) {
            ll a; cin >> a;
            sum += a;
            box[log2(a)]++;
        }
        if (n > sum) {
            cout << -1 << '\n';
            continue;
        }
        ll ans = 0;
        for (int i = 0; i < 64; i++) {
            if (n & (1LL << i)) {
                if (box[i]) {
                    box[i]--;
                }
                else {
                    while (!box[i]) i++, ans++;
                    box[i]--; i--;
                    continue;
                }
            }
            box[i+1] += box[i] / 2;
        }
        cout << ans << '\n';
    }
    return 0;
}