Problem J. Breakfast

이 문제는 주어진 공식을 기반으로 한 간단한 산술 연산을 요구합니다. 표현식의 결과를 계산한 후, 출력 형식에 맞게 소수점 둘째 자리까지 포맷팅하면 됩니다.

#include <iostream>
#include <iomanip>

int main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(nullptr);
    
    double base_value = 32.0;
    double multiplier = 0.6;
    double addition = 20.0;
    
    double final_result = base_value * multiplier + addition;
    
    std::cout << std::fixed << std::setprecision(2) << final_result << "\n";
    return 0;
}

Problem A. Paper Watering

이 문제의 핵심은 수학 연산을 신중하게 처리하는 데 있습니다. 어떤 수에 제곱근을 취했을 때, 그 수가 완전 제곱수가 아니라면 이후에 다시 제곱을 하더라도 원래 값과 달라지게 됩니다. 따라서 현재 수가 완전 제곱수인지 확인해야 합니다. 만약 완전 제곱수라면 제곱근을 취하고 연산 횟수를 차감하며, 그렇지 않다면 남은 연산 횟수를 최대한 활용하여 카운트를 증가시킨 후 반복문을 종료합니다.

#include <iostream>
#include <cmath>

using namespace std;

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

    long long initial_val, operations;
    if (!(cin >> initial_val >> operations)) return 0;

    long long total_count = (initial_val == 1) ? 1 : operations + 1;
    long long current_val = initial_val;
    long long remaining_ops = operations;

    while (current_val > 1 && remaining_ops > 0) {
        long long root_val = sqrt(current_val);
        total_count++;
        remaining_ops--;

        if (root_val * root_val == current_val || root_val == 1) {
            current_val = root_val;
        } else {
            total_count += remaining_ops;
            current_val = root_val;
            break; 
        }
    }

    cout << total_count << "\n";
    return 0;
}

Problem D. nIMgAME

이 문제는 1, 2, 3개의 아이템만 제거할 수 있는 님 게임(Nim game)의 변형입니다. 승리 조건은 남은 아이템의 XOR 합이 0이 되는 것이며, 이는 전체 합이 짝수여야 함을 의미합니다. 첫 번째 플레이어가 어떻게 행동하든, 두 번째 플레이어는 항상 그에 대응하여 전체 합의 홀짝성을 깨뜨릴 수 있습니다. 따라서 최적의 플레이를 가정할 때 첫 번째 플레이어는 필패하게 됩니다.

#include <iostream>

using namespace std;

void processTestCase() {
    int pile_size;
    cin >> pile_size;
    cout << "lose\n";
}

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

    int test_cases;
    if (cin >> test_cases) {
        while (test_cases--) {
            processTestCase();
        }
    }
    return 0;
}

Problem E. Checksum

매개변수 k가 최대 20으로 제한되어 있으므로, 가능한 모든 이진 상태를 무차별 대입 방식으로 열거할 수 있습니다. 또한 문제에서 n과 관련된 제약 조건이 주어지므로, 상태의 총 설정 비트 수는 n + k를 초과해서는 안 됩니다. 2^k까지의 모든 정수를 순회하며 비트 카운트 제약 조건을 기반으로 필터링하면 유효한 체크섬 문자열을 효율적으로 찾을 수 있습니다.

#include <iostream>
#include <string>

using namespace std;

void solveChecksum() {
    int max_len, target_k;
    cin >> max_len >> target_k;
    string input_str;
    cin >> input_str;

    int initial_ones = 0;
    for (char c : input_str) {
        if (c == '1') initial_ones++;
    }

    int limit = max_len + target_k;
    int max_state = 1 << target_k;

    for (int state = 0; state < max_state && state <= limit; ++state) {
        int bit_count = __builtin_popcount(state);
        if (bit_count + initial_ones == state) {
            string result = "";
            for (int i = target_k - 1; i >= 0; --i) {
                result += (state & (1 << i)) ? '1' : '0';
            }
            cout << result << "\n";
            return;
        }
    }
    cout << "None\n";
}

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

    int t;
    if (cin >> t) {
        while (t--) solveChecksum();
    }
    return 0;
}

Problem F. Factor

기약 분수가 k진법에서 유한 소수가 되기 위해서는, 분모의 소인수들이 k의 소인수들의 부분 집합이어야 합니다. 따라서 먼저 k와 p의 소인수분해를 수행합니다. 유효한 분모를 구성해야 하므로, k의 소인수(충분한 중복도 포함)와 p의 소인수를 사용하여 가능한 모든 곱을 생성할 수 있습니다. 그 후 깊이 우선 탐색(DFS)을 사용하여 주어진 상한선 x를 초과하지 않는 소인수 거듭제곱의 모든 조합을 열거합니다.

#include <iostream>
#include <vector>
#include <unordered_map>

using namespace std;

unordered_map<long long, int> prime_counts;

void extractPrimes(long long num, int multiplier) {
    for (long long i = 2; i * i <= num; ++i) {
        while (num % i == 0) {
            prime_counts[i] += multiplier;
            num /= i;
        }
    }
    if (num > 1) {
        prime_counts[num] += multiplier;
    }
}

long long valid_denominators = 0;
long long upper_bound;
vector<pair<long long, int>> primes_list;

void dfs(int idx, long long current_product) {
    if (idx == primes_list.size()) {
        valid_denominators++;
        return;
    }

    long long p = primes_list[idx].first;
    int max_power = primes_list[idx].second;
    long long temp_product = current_product;

    for (int i = 0; i <= max_power; ++i) {
        dfs(idx + 1, temp_product);
        if (temp_product > upper_bound / p) break;
        temp_product *= p;
    }
}

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

    long long p_val, x_val, k_val;
    if (!(cin >> p_val >> x_val >> k_val)) return 0;

    upper_bound = x_val;
    extractPrimes(k_val, 100);
    extractPrimes(p_val, 1);

    for (auto& entry : prime_counts) {
        primes_list.push_back(entry);
    }

    dfs(0, 1);
    cout << valid_denominators << "\n";

    return 0;
}

Problem L. Bracket Generation

문제 조건을 분석해 보면, 괄호를 첫 번째 연산으로 생성된 기본 쌍 ()와 두 번째 연산으로 확장된 구조 (...)로 분류할 수 있습니다. 첫 번째 연산은 엄격한 순서를 따르므로, i번째 기본 쌍은 앞서 i-1개의 쌍이 모두 확립되어야 합니다. 반면 두 번째 연산은 순서가 없으며 기존 기본 쌍을 확장할 수 있습니다. 주어진 괄호 문자열을 파싱하여 기본 쌍의 위치를 식별하면, 유효한 확장 시퀀스의 수를 계산할 수 있습니다. 총 경우의 수는 각 확장 단계에서 가능한 선택지의 곱으로 계산되며, 998244353으로 나눈 나머지를 구합니다.

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>

using namespace std;

const long long MOD = 998244353;

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

    string brackets;
    if (!(cin >> brackets)) return 0;

    vector<int> expansion_points;
    int fundamental_count = 0;

    for (size_t i = 0; i < brackets.length(); ++i) {
        if (brackets[i] == ')') {
            if (i > 0 && brackets[i - 1] == '(') {
                fundamental_count++;
            } else {
                expansion_points.push_back(fundamental_count);
            }
        }
    }

    long long total_ways = 1;
    reverse(expansion_points.begin(), expansion_points.end());

    for (size_t i = 0; i < expansion_points.size(); ++i) {
        long long choices = (fundamental_count - expansion_points[i] + 1 + i) % MOD;
        total_ways = (total_ways * choices) % MOD;
    }

    cout << total_ways << "\n";
    return 0;
}

Problem I. Password

dp[i]를 마지막 완전한 순열이 정확히 i 위치에서 끝나는 유효한 수열의 개수로 정의합니다. 최종 정답은 dp[n]이 됩니다. 상태 전이는 보조 배열 f[j]에 의존하는데, 이는 기존 완전한 순열 뒤에 j개의 원소를 추가할 때 중간에 또 다른 완전한 순열이 우발적으로 형성되지 않도록 하는 유효한 방법의 수를 나타냅니다.

f[j]를 계산하기 위해, j개 원소의 전체 순열(j!)에서 시작하여 완전한 순열이 조기에 형성되는 유효하지 않은 구성을 차감합니다. 이를 통해 f에 대한 점화식을 유도하며, 이어서 메인 dp 배열을 채우는 데 사용됩니다. 오버플로우를 방지하고 정확성을 보장하기 위해 조합 수학 및 모듈러 연산을 신중하게 처리해야 합니다.

#include <iostream>
#include <vector>

using namespace std;

const long long MOD = 998244353;
const int MAXN = 1000005;
long long factorial[MAXN];

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

    int n, k;
    if (!(cin >> n >> k)) return 0;

    factorial[0] = 1;
    for (int i = 1; i <= n; ++i) {
        factorial[i] = (factorial[i - 1] * i) % MOD;
    }

    if (n < k) {
        cout << 0 << "\n";
        return 0;
    }

    vector<long long> f(k + 1, 0);
    for (int i = 1; i <= k; ++i) {
        f[i] = factorial[i];
        for (int j = 1; j < i; ++j) {
            long long subtract = (factorial[j] * f[i - j]) % MOD;
            f[i] = (f[i] - subtract + MOD) % MOD;
        }
    }

    vector<long long> dp(n + 1, 0);
    dp[k] = factorial[k];
    for (int i = k + 1; i <= n; ++i) {
        for (int j = 1; j <= k; ++j) {
            dp[i] = (dp[i] + dp[i - j] * f[j]) % MOD;
        }
    }

    cout << dp[n] << "\n";
    return 0;
}