A. 구간 나누기

문자열 내에서 연속된 '1'은 서로 독립적인 구간으로 처리할 수 있다. 각 구간에 대해 최적의 분할 방식을 고려해야 한다. 길이가 \( k \) 인 연속된 1의 블록이 있을 때, 다음과 같은 전략이 최선이다:

• \( k \)가 홀수면, \( \frac{k+1}{2} \) 개의 단일 1로 나누며, 이때 결과는 \( \frac{k+1}{2} \).
• \( k \)가 짝수면, \( \frac{k}{2} - 1 \) 개의 단일 1과 하나의 두 연속 1 쌍으로 구성하며, 결과는 \( \frac{k}{2} - 1 + \sqrt{2} \).

모든 구간을 탐색하면서 위 규칙을 적용하고, 실수형으로 정밀하게 출력한다.

#include <iostream>
#include <vector>
#include <string>
#include <cmath>
#include <iomanip>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    string s;
    cin >> s;
    s = " " + s + "0"; // 양 끝에 보정 문자 추가
    int n = s.length();
    vector<int> lengths;
    int current = 0;

    for (int i = 1; i < n; ++i) {
        if (s[i] == '1') {
            current++;
        } else {
            if (current > 0) {
                lengths.push_back(current);
                current = 0;
            }
        }
    }

    double result = 0.0;
    for (int len : lengths) {
        while (len >= 2) {
            result += 1.0;
            len -= 2;
        }
        result += sqrt(len); // 남은 1개 또는 0개
    }

    cout << fixed << setprecision(13) << result << endl;
    return 0;
}

B. 퍼즐 조각 배치

직사각형 퍼즐의 네 모서리는 특정 조각(a)만 배치 가능하며, 변 상에는 b 또는 c 종류의 조각이 필요하다. 중심부는 d 조각으로 채운다. 중요한 관찰은:

• 네 귀퉁이에 a 조각이 필요하므로 최소 4개 필요.
• b와 c 조각은 인접해야 하며, 시계 방향 순서상 번갈아 등장해야 하므로 사용 횟수가 같아야 함.
• 따라서 b와 c 중 적은 수에 맞춰 대칭적으로 사용한다.

주어진 조각 수를 바탕으로 가능한 직사각형의 크기를 시뮬레이션하여 최대 면적을 계산한다.

#include <iostream>
#include <climits>
using namespace std;

int T, a, b, c, d;

int main() {
    cin >> T;
    while (T--) {
        cin >> a >> b >> c >> d;
        if (a < 4) {
            cout << 0 << '\n';
            continue;
        }

        // b와 c는 동일 개수만큼 사용 가능
        int max_use = min(b, c);
        int best = 0;

        for (int use = 0; use <= max_use; ++use) {
            // 가로 변에 use개, 세로 변에 최대한 많이 배치
            int vertical_space = d / (use ? use : 1); // use != 0 대비
            int vertical_use = min(vertical_space, max_use - use);
            int total_pieces = 4 + 2 * use + 2 * vertical_use + use * vertical_use;
            best = max(best, total_pieces);
        }
        cout << best << '\n';
    }
    return 0;
}

C. 비트 연산 조합

인접한 두 정수 \( x \), \( y \) 사이에 새로운 값을 삽입할 수 있으며, 이 값은 \( x \)와 \( y \)의 비트 연산 결과에 제한된다. 핵심은 인접 쌍마다 생성 가능한 모든 비트 패턴을 수집하는 것이다.

각 비트 위치에서 가능한 상태는:

• 둘 다 0 → 항상 0 유지
• 둘 다 1 → 다양한 조합 가능
• 0과 1 → XOR, AND 등을 통해 0/1 모두 생성 가능

실제로 다음 8가지 표현이 모두 생성 가능함이 증명된다: \( x, y, x|y, x\&y, x^y, (x^y)\&x, (x^y)\&y, 0 \). 이를 집합(set)에 저장해 중복 없이 카운트한다.

#include <iostream>
#include <set>
using namespace std;

int main() {
    int n;
    cin >> n;
    set<long long> results;
    results.insert(0);

    long long prev, curr;
    cin >> prev;
    results.insert(prev);

    for (int i = 1; i < n; ++i) {
        cin >> curr;
        results.insert(curr);
        results.insert(prev | curr);
        results.insert(prev & curr);
        results.insert(prev ^ curr);
        results.insert((prev ^ curr) & prev);
        results.insert((prev ^ curr) & curr);
        prev = curr;
    }

    cout << results.size() << endl;
    return 0;
}

D. XOR 정렬 조건

배열 \( a \)가 주어졌을 때, 어떤 \( x \)를 선택하면 \( a_i \oplus x \leq a_{i+1} \oplus x \)가 모든 \( i \)에 대해 성립하도록 하고 싶다.

핵심 아이디어: 가장 높은 비트부터 살펴보며, \( a_i \)와 \( a_{i+1} \)이 처음으로 다른 위치 \( pos \)를 찾는다.

• 만약 \( a_i \)의 그 비트가 0이고 \( a_{i+1} \)이 1이면, \( x \)의 해당 비트는 0이어야 한다.
• 반대로 \( a_i \)가 1이고 \( a_{i+1} \)가 0이면, \( x \)의 그 비트는 1이어야 한다.

이러한 제약 조건을 각 비트에 대해 기록하고, 충돌(0과 1 모두 필요)이 발생하면 해답 없음(-1). 그렇지 않으면 제약에 따라 비트를 설정하고 나머지는 0으로 채운다.

#include <iostream>
#include <vector>
using namespace std;

void solve() {
    int n;
    cin >> n;
    vector<long long> arr(n + 1);
    for (int i = 1; i <= n; ++i) {
        cin >> arr[i];
    }

    // 각 비트 위치에서 x의 해당 비트가 0 또는 1일 수 있는지 여부
    bool canBeZero[61], canBeOne[61];
    for (int i = 0; i <= 60; ++i) {
        canBeZero[i] = canBeOne[i] = true;
    }

    for (int i = 1; i < n; ++i) {
        long long u = arr[i], v = arr[i + 1];
        for (int j = 60; j >= 0; --j) {
            int bitU = (u >> j) & 1;
            int bitV = (v >> j) & 1;
            if (bitU != bitV) {
                if (bitU == 1) {
                    canBeZero[j] = false; // x_j는 1이어야 함
                } else {
                    canBeOne[j] = false; // x_j는 0이어야 함
                }
                break;
            }
        }
    }

    long long x = 0;
    for (int i = 60; i >= 0; --i) {
        if (!canBeZero[i] && !canBeOne[i]) {
            cout << -1 << '\n';
            return;
        }
        if (!canBeZero[i]) {
            x |= (1LL << i);
        }
    }
    cout << x << '\n';
}

int main() {
    int T;
    cin >> T;
    while (T--) {
        solve();
    }
    return 0;
}