A. 상자 탑 쌓기

같은 크기의 상자만 존재하므로 각 상자가 견딜 수 있는 최대 상자 수를 계산하면 된다. 이 값을 c로 표기하면, 최대 스택 높이는 c+1이 된다. 전체 상자 수 n을 나누어 최소한의 스택 수를 계산한다.

코드 보기

<!-- 깊은 어둠을 바라보는 자, 어둠도 그를 바라보리라 -->
#include <bits/stdc++.h>

using namespace std;

int main() {
    int test_cases;
    cin >> test_cases;
    while (test_cases--) {
        int box_count, max_weight, threshold;
        cin >> box_count >> max_weight >> threshold;
        
        int max_per_stack = (threshold / max_weight) + 1;
        cout << (box_count + max_per_stack - 1) / max_per_stack << '\n';
    }
    return 0;
}

B. 숫자의 아름다움

함수 f(x)의 결과가 원래 값과 같아야 한다. 이는 결과가 한 자리 수임을 의미한다. 각 자릿수의 영향력을 계산해 가장 큰 영향력을 가진 자릿수부터 선택하면 최적 해를 찾을 수 있다.

코드 보기

<!-- 깊은 어둠을 바라보는 자, 어둠도 그를 바라보리라 -->
#include <bits/stdc++.h>

using namespace std;

int main() {
    int test_cases;
    cin >> test_cases;
    while (test_cases--) {
        string number_str;
        cin >> number_str;
        int length = number_str.length();
        int digit_values[25] = {0};
        
        int total_sum = 0;
        for (int i = 0; i < length; ++i) {
            digit_values[i] = number_str[i] - '0';
            total_sum += digit_values[i];
        }
        
        digit_values[0]--;
        sort(digit_values, digit_values + length, greater<int>());
        
        int selected = 1;
        while (total_sum > 9) {
            total_sum -= digit_values[selected++];
        }
        
        cout << selected - 1 << '\n';
    }
    return 0;
}

C. 테스트 데이터 생성기

이 문제는 이진 비트 연산에 초점을 맞춘다. 특정 비트 패턴만 사용할 수 있으므로, 해당 비트에 해당하는 값들을 분리해 처리한다. 각 비트의 최소 사용 횟수를 계산하고, 이진 탐색으로 최소 배열 길이를 결정한다.

코드 보기

<!-- 깊은 어둠을 바라보는 자, 어둠도 그를 바라보리라 -->
#include <bits/stdc++.h>

#define int long long

using namespace std;

int base[61];

int get_value(int x, int y) {
    if (x > y) swap(x, y);
    return base[y - x];
}

bool check(int limit, int* gs, int* bits, int bit_count) {
    int current = gs[bit_count];
    for (int i = bit_count; i >= 1; --i) {
        if (current <= limit) {
            current = gs[i-1];
            continue;
        }
        int overflow = current - limit;
        current = gs[i-1] + overflow * get_value(bits[i], bits[i-1]);
    }
    return current <= limit;
}

int main() {
    base[0] = 1;
    for (int i = 1; i <= 60; ++i)
        base[i] = base[i-1] * 2;
    
    int test_cases;
    cin >> test_cases;
    while (test_cases--) {
        int target, mask;
        cin >> target >> mask;
        
        int bits[65] = {0}, bit_count = -1;
        int target_bits[65] = {0}, target_count = -1;
        
        int temp = 0;
        while (mask) {
            if (mask & 1) bits[++bit_count] = temp;
            mask >>= 1;
            temp++;
        }
        
        temp = 0;
        while (target) {
            if (target & 1) target_bits[++target_count] = temp;
            target >>= 1;
            temp++;
        }
        
        if (bits[0] > target_bits[0]) {
            cout << "-1\n";
            continue;
        }
        
        int gs[65] = {0};
        for (int i = 0; i <= target_count; ++i) {
            int idx = upper_bound(bits, bits + bit_count + 1, target_bits[i]) - bits - 1;
            gs[idx] += get_value(target_bits[i], bits[idx]);
        }
        
        int low = 1, high = 0;
        for (int i = 0; i <= bit_count; ++i)
            high = max(high, gs[i]);
        
        while (low < high) {
            int mid = (low + high) / 2;
            if (check(mid, gs, bits, bit_count)) high = mid;
            else low = mid + 1;
        }
        cout << low << '\n';
    }
    return 0;
}

D. 나누어지는 게임

각 수의 약수 개수를 계산해 Alice와 Bob의 선택 가능 수를 판단한다. Alice는 약수가 존재하는 수, Bob은 약수가 모두 포함되지 않는 수를 선택할 수 있다. 두 사람의 선택 수를 비교해 승패를 결정한다.

코드 보기

<!-- 깊은 어둠을 바라보는 자, 어둠도 그를 바라보리라 -->
#include <bits/stdc++.h>

using namespace std;

int read() {
    int x = 0, y = 1;
    char ch = getchar();
    while (ch > '9' || ch < '0') {
        if (ch == '-') y = -1;
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9') {
        x = x * 10 + ch - '0';
        ch = getchar();
    }
    return x * y;
}

void print(int x) {
    if (x < 0) x = -x, putchar('-');
    if (x > 9) print(x / 10);
    putchar(x % 10 + '0');
}

int main() {
    int test_cases;
    cin >> test_cases;
    while (test_cases--) {
        int a_size, b_size;
        cin >> a_size >> b_size;
        
        int array_a[1000005] = {0}, array_b[1000005] = {0};
        for (int i = 1; i <= a_size; ++i) array_a[i] = read();
        for (int i = 1; i <= b_size; ++i) array_b[i] = read();
        
        int max_val = a_size + b_size;
        sort(array_a + 1, array_a + a_size + 1);
        a_size = unique(array_a + 1, array_a + a_size + 1) - array_a - 1;
        sort(array_b + 1, array_b + b_size + 1);
        
        int divisor_counts[2000005] = {0};
        for (int i = 1; i <= a_size; ++i) {
            int val = array_a[i];
            for (int j = val; j <= max_val; j += val)
                divisor_counts[j]++;
        }
        
        int alice_count = 0, bob_count = 0;
        for (int i = 1; i <= b_size; ++i) {
            if (divisor_counts[array_b[i]] != 0) alice_count++;
            if (divisor_counts[array_b[i]] != a_size) bob_count++;
        }
        
        int common = alice_count + bob_count - b_size;
        alice_count -= common;
        bob_count -= common;
        if (common % 2 == 1) alice_count++;
        
        if (alice_count > bob_count) cout << "Alice";
        else cout << "Bob";
        putchar('\n');
        
        for (int i = 1; i <= a_size; ++i) {
            int val = array_a[i];
            for (int j = val; j <= max_val; j += val)
                divisor_counts[j]--;
        }
    }
    return 0;
}