Arithmetic Series Reduction and Constant-Time Evaluation

Computing the scaled average of a consecutive integer sequence from 1 to $N$ requires evaluating $\frac{10000 \sum_{i=1}^{N} i}{N}$. The summation $\sum_{i=1}^{N} i$ resolves to the triangular number formula $\frac{N(N+1)}{2}$. Substituting this into the original expression yields: $$ \frac{10000}{N} \cdot \frac{N(N+1)}{2} = 5000(N+1) $$ This algebraic simplification eliminates the need for iteration, reducing the computational complexity to $O(1)$ and preventing potential overflow during intermediate summation.

#include <iostream>

int main() {
    long long sequence_length;
    if (std::cin >> sequence_length) {
        std::cout << 5000LL * (sequence_length + 1) << '\n';
    }
    return 0;
}

Wildcard String Equivalence with Restricted Substitution

Determining whether two character sequences can be made identical involves handling a special wildcard symbol (@) that maps to any character within a fixed alphabet set ("atcoder"). Equivalence is established under two strict conditions:

1. Both sequences must share identical lengths.
2. For every index, the characters must either match exactly, or at least one side must be a wildcard while the oppposing character exists within the permitted substitution set.

The validation iterates through both strings simultaneously, applying these constraints positionally.

#include <iostream>
#include <string>
#include <string_view>

bool can_match(std::string_view lhs, std::string_view rhs) {
    if (lhs.length() != rhs.length()) return false;
    
    constexpr std::string_view valid_chars = "atcoder";
    for (size_t idx = 0; idx < lhs.length(); ++idx) {
        char c1 = lhs[idx];
        char c2 = rhs[idx];
        
        if (c1 == c2) continue;
        
        bool left_is_wild = (c1 == '@');
        bool right_is_wild = (c2 == '@');
        
        if (left_is_wild && right_is_wild) continue;
        if (left_is_wild && valid_chars.find(c2) != std::string_view::npos) continue;
        if (right_is_wild && valid_chars.find(c1) != std::string_view::npos) continue;
        
        return false;
    }
    return true;
}

int main() {
    std::string str_a, str_b;
    std::cin >> str_a >> str_b;
    std::cout << (can_match(str_a, str_b) ? "You can win" : "You will lose") << '\n';
    return 0;
}

Greedy Ordering for Recursive Averaging

Given a collection of numerical values, selecting $K$ elements to maximize the result of the recursive operation $C \leftarrow \frac{C + v}{2}$ (initialized at $C=0$) requires analyzing the weight distribution. Expanding the recurrence for a chosen sequence $v_1, v_2, \dots, v_K$ reveals: $$ C_K = \frac{v_1}{2^K} + \frac{v_2}{2^{K-1}} + \dots + \frac{v_K}{2^1} $$ Later elements receive exponentially higher weights. To maximize the final value, the algorithm must select the $K$ largest available numbers and process them in strictly ascending order. Direct evaluation of the closed-form sum risks precision degradation and exponent overflow. Instead, applying the recurrence iteratively maintains numerical stability within standard floating-point types.

#include <iostream>
#include <vector>
#include <algorithm>
#include <iomanip>

int main() {
    int total_count, select_count;
    std::cin >> total_count >> select_count;
    
    std::vector<int> pool(total_count);
    for (int& val : pool) std::cin >> val;
    
    // Sort descending to easily extract the largest K elements
    std::sort(pool.begin(), pool.end(), std::greater<int>());
    
    // Extract top K and reverse to process in ascending order
    std::vector<int> chosen(pool.begin(), pool.begin() + select_count);
    std::reverse(chosen.begin(), chosen.end());
    
    double current_avg = 0.0;
    for (int val : chosen) {
        current_avg = (current_avg + val) / 2.0;
    }
    
    std::cout << std::fixed << std::setprecision(10) << current_avg << '\n';
    return 0;
}

Inclusion-Exclusion for Exact Bounding Box Enumeration

Calculating the number of ways too place $L$ red and $D$ blue items on an $R \times C$ grid such that their minimal enclosing rectangle is exactly $X \times Y$ involves combinatorial placement constrained by boundary conditions.

First, compute the raw placements within a fixed $X \times Y$ region: $\binom{XY}{L} \times \binom{XY-L}{D}$. However, this count includes configurations where items cluster within smaller sub-rectangles, violating the "minimal" requirement. To isolate exact dimensions, apply the Principle of Inclusion-Exclusion (PIE) across the four boundaries (top, bottom, left, right). Contracting edges reduces the available area, and alternating addition/subtraction of these contracted cases cancels out invalid configurations.

The coefficient for each contracted state corresponds to $\binom{4}{k}$, where $k$ is the number of shrunk edges. The final count is multiplied by the number of valid positions for an $X \times Y$ rectangle within the $R \times C$ grid: $(R - X + 1)(C - Y + 1)$. All calculations are performed modulo $10^9 + 7$ using precomputed factorials for efficient combination queries.

#include <iostream>
#include <vector>

constexpr int MOD = 1'000'000'007;
constexpr int MAX_VAL = 1'000'005;

int mod_add(int a, int b) {
    int res = (a + b) % MOD;
    return res < 0 ? res + MOD : res;
}

int mod_mul(long long a, long long b) {
    return static_cast<int>((a * b) % MOD);
}

std::vector<int> fact(MAX_VAL), inv_fact(MAX_VAL);

int power(int base, int exp) {
    int res = 1;
    while (exp > 0) {
        if (exp & 1) res = mod_mul(res, base);
        base = mod_mul(base, base);
        exp >>= 1;
    }
    return res;
}

void precompute_factorials() {
    fact[0] = inv_fact[0] = 1;
    for (int i = 1; i < MAX_VAL; ++i) {
        fact[i] = mod_mul(fact[i - 1], i);
    }
    inv_fact[MAX_VAL - 1] = power(fact[MAX_VAL - 1], MOD - 2);
    for (int i = MAX_VAL - 2; i > 0; --i) {
        inv_fact[i] = mod_mul(inv_fact[i + 1], i + 1);
    }
}

int nCr(int n, int r) {
    if (r < 0 || r > n) return 0;
    return mod_mul(fact[n], mod_mul(inv_fact[r], inv_fact[n - r]));
}

int count_arrangements(int area, int red, int blue) {
    if (area < red + blue) return 0;
    return mod_mul(nCr(area, red), nCr(area - red, blue));
}

int main() {
    precompute_factorials();
    
    int grid_h, grid_w, box_h, box_w, cnt_blue, cnt_red;
    std::cin >> grid_h >> grid_w >> box_h >> box_w >> cnt_blue >> cnt_red;
    
    int pie_sum = 0;
    
    // k=0: Original box
    pie_sum = mod_add(pie_sum, count_arrangements(box_h * box_w, cnt_red, cnt_blue));
    
    // k=1: Shrink 1 edge (4 combinations)
    pie_sum = mod_add(pie_sum, -count_arrangements((box_h - 1) * box_w, cnt_red, cnt_blue));
    pie_sum = mod_add(pie_sum, -count_arrangements((box_h - 1) * box_w, cnt_red, cnt_blue));
    pie_sum = mod_add(pie_sum, -count_arrangements(box_h * (box_w - 1), cnt_red, cnt_blue));
    pie_sum = mod_add(pie_sum, -count_arrangements(box_h * (box_w - 1), cnt_red, cnt_blue));
    
    // k=2: Shrink 2 edges (6 combinations)
    pie_sum = mod_add(pie_sum, count_arrangements((box_h - 1) * (box_w - 1), cnt_red, cnt_blue));
    pie_sum = mod_add(pie_sum, count_arrangements((box_h - 1) * (box_w - 1), cnt_red, cnt_blue));
    pie_sum = mod_add(pie_sum, count_arrangements((box_h - 1) * (box_w - 1), cnt_red, cnt_blue));
    pie_sum = mod_add(pie_sum, count_arrangements((box_h - 1) * (box_w - 1), cnt_red, cnt_blue));
    pie_sum = mod_add(pie_sum, count_arrangements((box_h - 2) * box_w, cnt_red, cnt_blue));
    pie_sum = mod_add(pie_sum, count_arrangements(box_h * (box_w - 2), cnt_red, cnt_blue));
    
    // k=3: Shrink 3 edges (4 combinations)
    pie_sum = mod_add(pie_sum, -count_arrangements((box_h - 2) * (box_w - 1), cnt_red, cnt_blue));
    pie_sum = mod_add(pie_sum, -count_arrangements((box_h - 2) * (box_w - 1), cnt_red, cnt_blue));
    pie_sum = mod_add(pie_sum, -count_arrangements((box_h - 1) * (box_w - 2), cnt_red, cnt_blue));
    pie_sum = mod_add(pie_sum, -count_arrangements((box_h - 1) * (box_w - 2), cnt_red, cnt_blue));
    
    // k=4: Shrink 4 edges (1 combination)
    pie_sum = mod_add(pie_sum, count_arrangements((box_h - 2) * (box_w - 2), cnt_red, cnt_blue));
    
    int valid_positions = mod_mul(grid_h - box_h + 1, grid_w - box_w + 1);
    std::cout << mod_mul(pie_sum, valid_positions) << '\n';
    
    return 0;
}