Problem A: Building Height Comparison

Given an array of building heights, find the first building taller than the first one.

#include <cstdio>
const int MAX_SIZE = 105;
int heights[MAX_SIZE];

int main() {
    int n;
    scanf("%d", &n);
    int result = -1;
    for (int i = 1; i <= n; i++) {
        scanf("%d", &heights[i]);
        if (heights[i] > heights[1] && result == -1) 
            result = i;
    }
    printf("%d\n", result);
    return 0;
}

Problem B: Amusement Park Ride Allocation

Simulate group allocations to rides based on capacity constraints.

#include <cstdio>
int main() {
    int n, capacity, current = 0, count = 0;
    scanf("%d%d", &n, &capacity);
    for (int i = 0; i < n; i++) {
        int group;
        scanf("%d", &group);
        if (current < group) {
            current = capacity;
            count++;
        }
        current -= group;
    }
    printf("%d\n", count);
    return 0;
}

Problem C: Modular Pair Summation

Compute sum of all pairs modulo 10^8 after sorting and using two pointers.

#include <cstdio>
#include <algorithm>
using namespace std;
const int MAX_N = 300005;
const long long MOD = 100000000;
long long arr[MAX_N], prefix[MAX_N];

int main() {
    int n;
    scanf("%d", &n);
    for (int i = 0; i < n; i++) scanf("%lld", &arr[i]);
    sort(arr, arr + n);
    long long total = 0;
    int right = n;
    for (int i = 0; i < n; i++) {
        total += arr[i] * i + prefix[i];
        while (right > 0 && arr[right-1] + arr[i] >= MOD) right--;
        total -= (n - right) * MOD;
        prefix[i+1] = prefix[i] + arr[i];
    }
    printf("%lld\n", total);
    return 0;
}

Problem D: Digit Concatenation Sum

Calculate sum of all digit concatenations using prefix sums and power-of-10 multipliers.

#include <cstdio>
const int MAX = 200005;
const int MOD = 998244353;
long long nums[MAX], psum[MAX], powers[20];

int main() {
    powers[0] = 1;
    for (int i = 1; i < 15; i++) powers[i] = powers[i-1] * 10 % MOD;
    int n;
    scanf("%d", &n);
    long long res = 0;
    for (int i = 0; i < n; i++) {
        scanf("%lld", &nums[i]);
        long long temp = nums[i];
        int digits = 0;
        while (temp) digits++, temp /= 10;
        res = (res + psum[i] * powers[digits] + nums[i] * i) % MOD;
        psum[i+1] = (psum[i] + nums[i]) % MOD;
    }
    printf("%lld\n", res);
    return 0;
}

Problem E: Longest Common Prefix Sum

Use a trie to accmuulate LCP sums efficeintly during insertion.

#include <cstdio>
#include <cstring>
const int NODES = 300005;
int trie[NODES][26], count[NODES], idx;
long long result;

void insert(char* s) {
    int node = 0, len = strlen(s);
    for (int i = 0; i < len; i++) {
        int c = s[i] - 'a';
        if (!trie[node][c]) trie[node][c] = ++idx;
        node = trie[node][c];
        count[node]++;
    }
}

long long query(char* s) {
    int node = 0, len = strlen(s);
    long long sum = 0;
    for (int i = 0; i < len; i++) {
        int c = s[i] - 'a';
        if (!trie[node][c]) break;
        node = trie[node][c];
        sum += count[node];
    }
    return sum;
}

int main() {
    int n;
    scanf("%d", &n);
    char str[100005];
    for (int i = 0; i < n; i++) {
        scanf("%s", str);
        result += query(str);
        insert(str);
    }
    printf("%lld\n", result);
    return 0;
}

Problem G: Dynamic Programming with Spatial Constraints

Optimize DP using Fenwick trees for prefix and suffix max queries.

#include <cstdio>
#include <algorithm>
using namespace std;
const int MAX_T = 200005;
const long long INF = -1e18;
long long dp[MAX_T], rewards[MAX_T];
int towns[MAX_T];

struct Fenwick {
    long long tree[MAX_T];
    void init(int size) {
        for (int i = 0; i <= size; i++) tree[i] = INF;
    }
    void update(int i, long long v) {
        for (; i < MAX_T; i += i & -i) tree[i] = max(tree[i], v);
    }
    long long query(int i) {
        long long best = INF;
        for (; i > 0; i -= i & -i) best = max(best, tree[i]);
        return best;
    }
} leftTree;

struct FenwickReverse {
    long long tree[MAX_T];
    void init(int size) {
        for (int i = 0; i <= size; i++) tree[i] = INF;
    }
    void update(int i, long long v) {
        for (; i > 0; i -= i & -i) tree[i] = max(tree[i], v);
    }
    long long query(int i) {
        long long best = INF;
        for (; i < MAX_T; i += i & -i) best = max(best, tree[i]);
        return best;
    }
} rightTree;

int main() {
    int n, m;
    long long cost;
    scanf("%d%lld%d", &n, &cost, &m);
    leftTree.init(n); rightTree.init(n);
    for (int i = 1; i <= n; i++) dp[i] = INF;
    dp[1] = 0;
    leftTree.update(1, cost);
    rightTree.update(1, n * cost);
    long long answer = 0;
    for (int i = 0; i < m; i++) {
        int t; long long p;
        scanf("%d%lld", &t, &p);
        long long leftVal = leftTree.query(t) - t * cost;
        long long rightVal = rightTree.query(t) - (n - t + 1) * cost;
        dp[t] = max(leftVal, rightVal) + p;
        leftTree.update(t, dp[t] + t * cost);
        rightTree.update(t, dp[t] + (n - t + 1) * cost);
        answer = max(answer, dp[t]);
    }
    printf("%lld\n", answer);
    return 0;
}