A. 기호 기반 계산 시스템 구현

주어진 명령어 집합(정의, 곱셈, 나눗셈, 덧셈, 뺄셈, 모듈러 연산)을 기반으로 간단한 식 계산 시스템을 구현한다. 각 명령어는 변수에 대한 연산을 수행하며, 결과는 항상 모듈러 연산을 통해 유지된다.

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

typedef long long LL;
const LL MOD = 1LL << 47;

LL fast_multiply(LL a, LL b) {
    LL result = 0;
    while (b) {
        if (b & 1) result = (result + a) % MOD;
        a = (a * 2) % MOD;
        b >>= 1;
    }
    return result % MOD;
}

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

    string command, var1, var2;
    map<string, LL> variables;

    while (cin >> command) {
        if (command == "def") {
            cin >> var1 >> var2;
            variables[var1] = stoll(var2) % MOD;
            cout << var1 << " = " << variables[var1] << '\n';
        } else if (command == "add") {
            cin >> var1 >> var2;
            variables[var1] = (variables[var1] + variables[var2]) % MOD;
            cout << var1 << " = " << variables[var1] << '\n';
        } else if (command == "sub") {
            cin >> var1 >> var2;
            variables[var1] = (variables[var1] - variables[var2] + MOD) % MOD;
            cout << var1 << " = " << variables[var1] << '\n';
        } else if (command == "mul") {
            cin >> var1 >> var2;
            variables[var1] = fast_multiply(variables[var1], variables[var2]) % MOD;
            cout << var1 << " = " << variables[var1] << '\n';
        } else if (command == "div") {
            cin >> var1 >> var2;
            variables[var1] = (variables[var1] / variables[var2] + MOD) % MOD;
            cout << var1 << " = " << variables[var1] << '\n';
        } else if (command == "mod") {
            cin >> var1 >> var2;
            variables[var1] = variables[var1] % variables[var2];
            cout << var1 << " = " << variables[var1] << '\n';
        }
    }

    return 0;
}

D. 동적 조건 하에서의 누적 곱 계산

각 단계에서 값을 곱하거나 특정 이전 단계의 값을 무시하는 방식으로 진행되는 연산 시뮬레이션. 선형 시간 내에 모든 상태를 관리하기 위해 세그먼트 트리를 활용하여 구간 곱을 효율적으로 계산한다.

#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;

typedef long long LL;
const int MAXN = 1e5 + 5;
const int MOD = 1e9 + 7;

struct SegmentTree {
    int l, r;
    LL mul;
} tree[MAXN * 4];

void push_up(int rt) {
    tree[rt].mul = (tree[rt << 1].mul * tree[rt << 1 | 1].mul) % MOD;
}

void build(int rt, int left, int right) {
    tree[rt].l = left;
    tree[rt].r = right;
    tree[rt].mul = 1;
    if (left == right) return;
    int mid = (left + right) / 2;
    build(rt << 1, left, mid);
    build(rt << 1 | 1, mid + 1, right);
    push_up(rt);
}

void update(int rt, int pos, int val) {
    if (tree[rt].l == pos && tree[rt].r == pos) {
        tree[rt].mul = val;
        return;
    }
    int mid = (tree[rt].l + tree[rt].r) / 2;
    if (pos <= mid) update(rt << 1, pos, val);
    else update(rt << 1 | 1, pos, val);
    push_up(rt);
}

int main() {
    int T;
    scanf("%d", &T);
    while (T--) {
        int Q, M;
        scanf("%d%d", &Q, &M);
        build(1, 1, Q);
        char op[2];
        int x;
        for (int i = 1; i <= Q; ++i) {
            scanf("%s%d", op, &x);
            if (op[0] == 'M') {
                update(1, i, x);
            } else {
                update(1, x, 1);
            }
            printf("%lld\n", tree[1].mul);
        }
    }
    return 0;
}

E. 제약 조건이 있는 최단 경로 탐색

노드마다 이동 가능한 시간 구간이 정해져 있으며, 그 구간 내에서만 이동 가능하다. 이를 고려하여 다익스트라 알고리즘을 확장하여, 도착 시점이 해당 노드의 주기 구간 내에서 짝수 또는 홀수 배인지 판단하고, 필요시 지연을 추가한다.

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

typedef long long LL;
const int MAXN = 1005;
const LL INF = 1e18;

struct Edge {
    int to;
    LL weight;
};

vector<Edge> graph[MAXN];
LL time_limit[MAXN];
LL dist[MAXN];
bool visited[MAXN];

void dijkstra(int start, int end_node) {
    priority_queue<pair<LL, int>, vector<pair<LL, int>>, greater<pair<LL, int>>> pq;
    memset(dist, INF, sizeof(dist));
    memset(visited, false, sizeof(visited));
    dist[start] = 0;
    pq.push({0, start});

    while (!pq.empty()) {
        int u = pq.top().second;
        pq.pop();
        if (visited[u]) continue;
        visited[u] = true;

        for (auto &e : graph[u]) {
            int v = e.to;
            LL cost = dist[u] + e.weight;
            if (time_limit[v] > 0 && v != end_node) {
                LL k = cost / time_limit[v];
                if (k % 2 == 1) cost = (k + 1) * time_limit[v];
            }
            if (cost < dist[v]) {
                dist[v] = cost;
                pq.push({cost, v});
            }
        }
    }
}

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

    int T;
    cin >> T;
    while (T--) {
        int N, M;
        cin >> N >> M;
        for (int i = 1; i <= N; ++i) {
            cin >> time_limit[i];
        }
        for (int i = 0; i < M; ++i) {
            int u, v;
            LL w;
            cin >> u >> v >> w;
            graph[u].push_back({v, w});
            graph[v].push_back({u, w});
        }
        int S, E;
        cin >> S >> E;
        dijkstra(S, E);
        cout << dist[E] << '\n';
    }

    return 0;
}

G. 두 사각형의 면적 교차 및 합 계산

두 사각형의 좌표와 크기를 입력받아, 면적의 교차 부분과 합 부분을 계산하고, 교차 비율을 출력한다. 범위 확인 후, 수학적 공식을 사용하여 정확한 비율을 도출.

#include <cstdio>
#include <algorithm>
using namespace std;

int main() {
    int T;
    scanf("%d", &T);
    while (T--) {
        int x1, y1, w1, h1;
        int x2, y2, w2, h2;
        scanf("%d%d%d%d", &x1, &y1, &w1, &h1);
        scanf("%d%d%d%d", &x2, &y2, &w2, &h2);

        LL area1 = (LL)w1 * h1;
        LL area2 = (LL)w2 * h2;
        LL total_area = area1 + area2;

        int overlap_x = max(0, min(x1 + w1, x2 + w2) - max(x1, x2));
        int overlap_y = max(0, min(y1 + h1, y2 + h2) - max(y1, y2));
        LL intersection = (LL)overlap_x * overlap_y;

        double ratio = 1.0 * intersection / (total_area - intersection);
        printf("%.2f\n", ratio);
    }
    return 0;
}

H. 랜덤 피해 분배 확률 계산

총 피해량이 주어졌을 때, 적의 보조 유닛에 최소한의 피해가 들어가도록 하는 경우의 수를 이항 계수를 이용해 계산. 전체 가능성은 2^N이며, 보조 유닛을 죽이기 위한 최소 피해량 조건을 만족하는 경우의 수를 전처리하여 빠르게 계산.

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

typedef long long LL;
const int MOD = 1e9 + 7;
const int MAXN = 1005;

LL fact[MAXN], inv_fact[MAXN];
LL pow2[MAXN], inv_pow2[MAXN];

LL mod_pow(LL base, LL exp) {
    LL res = 1;
    while (exp) {
        if (exp & 1) res = res * base % MOD;
        base = base * base % MOD;
        exp >>= 1;
    }
    return res;
}

void precompute() {
    fact[0] = 1;
    for (int i = 1; i < MAXN; ++i)
        fact[i] = fact[i-1] * i % MOD;
    inv_fact[MAXN-1] = mod_pow(fact[MAXN-1], MOD-2);
    for (int i = MAXN-2; i >= 0; --i)
        inv_fact[i] = inv_fact[i+1] * (i+1) % MOD;
    for (int i = 0; i < MAXN; ++i) {
        pow2[i] = mod_pow(2, i);
        inv_pow2[i] = mod_pow(pow2[i], MOD-2);
    }
}

LL combination(int n, int r) {
    if (r < 0 || r > n) return 0;
    return fact[n] * inv_fact[r] % MOD * inv_fact[n-r] % MOD;
}

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

    int T;
    cin >> T;
    while (T--) {
        int n, m;
        cin >> n >> m;
        LL total = pow2[n];
        LL sum = 0;
        for (int i = m; i <= n; ++i)
            sum = (sum + combination(n, i)) % MOD;
        LL ans = (total - sum + MOD) % MOD;
        ans = ans * inv_pow2[n] % MOD;
        cout << ans << '\n';
    }
    return 0;
}

J. 순서 기반 신뢰도 확률 계산

사람들이 일렬로 연결되어 있으며, 한 사람에게 과자를 주면 자신과 그 아래 계층의 모든 사람이 진실을 말하게 된다. 과자 수가 주어졌을 때, 진실을 말하는 사람 수의 기대값을 이론적으로 계산. 조합 수의 성질을 활용해 간단한 공식으로 해결.

#include <cstdio>
using namespace std;

typedef long long LL;
const int MOD = 1e9 + 7;

LL mod_pow(LL base, LL exp) {
    LL res = 1;
    while (exp) {
        if (exp & 1) res = res * base % MOD;
        base = base * base % MOD;
        exp >>= 1;
    }
    return res;
}

int main() {
    int T;
    scanf("%d", &T);
    while (T--) {
        LL n, m;
        scanf("%lld%lld", &n, &m);
        if (m >= n) {
            printf("%lld\n", n);
            continue;
        }
        LL inv_m_plus_1 = mod_pow(m + 1, MOD - 2);
        LL result = (m * (n + 1) % MOD) * inv_m_plus_1 % MOD;
        printf("%lld\n", result);
    }
    return 0;
}