Problem A: Trapezoid Area

Given the upper base $a$, lower base $b$, and height $h$ of a trapezoid, the area is calculated using the formula:

$$\text{Area} = \frac{(a + b) \times h}{2}$$

Problem B: Card Game for Three

Three players, A, B, and C, each start with a string of cards. Starting with player A, they draw cards in a sequence. If a player draws 'a', the next turn belongs to player A; if 'b', to player B; if 'c', to player C. The game ends when a player needs to draw a card but their specific deck is empty.

To solve this, simulate the process using three queues. The complexity is $O(N)$ where $N$ is the total number of cards.

#include <iostream>
#include <string>
#include <queue>
#include <vector>

char solve_game(std::vector<std::string>& decks) {
    std::queue<char> q[3];
    for (int i = 0; i < 3; ++i) {
        for (char c : decks[i]) q[i].push(c);
    }
    int turn = 0;
    while (true) {
        if (q[turn].empty()) return 'A' + turn;
        int next = q[turn].front() - 'a';
        q[turn].pop();
        turn = next;
    }
}

Problem C: Many Formulas

Given a string of digits, insert zero or more '+' signs between them to form a valid sum. Calculate the total of all possible valid expressions.

Since the string length is at most 10, there are $2^{|S|-1}$ possible configurations for placing the '+' signs. We can iterate through every bitmask representation to evaluate each configuration.

#include <iostream>
#include <string>

long long evaluate_sum(const std::string& s) {
    int n = s.length();
    long long total = 0;
    for (int i = 0; i < (1 << (n - 1)); ++i) {
        long long current_sum = 0, current_num = s[0] - '0';
        for (int j = 0; j < n - 1; ++j) {
            if ((i >> j) & 1) {
                current_sum += current_num;
                current_num = s[j + 1] - '0';
            } else {
                current_num = current_num * 10 + (s[j + 1] - '0');
            }
        }
        total += current_sum + current_num;
    }
    return total;
}

Problem D: Snuke's Coloring

Given an $H \times W$ grid, $N$ specified cells are colored black. We need to count how many $3 \times 3$ subgrids contain exactly $k$ black cells, for all $k \in [0, 9]$.

Given the constraints $H, W \le 10^9$ and $N \le 10^5$, we only consider $3 \times 3$ subgrids that contain at least one black cell. A black cell at $(r, c)$ affects all $3 \times 3$ subgrids whose top-left corners range from $(r-2, c-2)$ to $(r, c)$.

1. Use a hash map to count the number of black cells in each $3 \times 3$ subgrid identified by its top-left corner.
2. Let $K$ be the number of subgrids that contain atleast one black cell.
3. The number of subgrids with zero black cells is $(H-2) \times (W-2) - K$.

#include <map>
#include <vector>

void count_subgrids(int H, int W, const std::vector<std::pair<int, int>>& points) {
    std::map<std::pair<int, int>, int> counts;
    for (auto& p : points) {
        for (int i = p.first - 2; i <= p.first; ++i) {
            for (int j = p.second - 2; j <= p.second; ++j) {
                if (i >= 1 && i <= H - 2 && j >= 1 && j <= W - 2) {
                    counts[{i, j}]++;
                }
            }
        }
    }
    std::vector<long long> result(10, 0);
    for (auto const& [pos, count] : counts) {
        result[count]++;
    }
    result[0] = (long long)(H - 2) * (W - 2) - counts.size();
}