Month Transition Calculation

Problem Statement

Given an integer current_month representing a month (1 through 12), compute the subsequent month in the annual cycle.

Solution Approach

Months follow a cyclic pattern with base 12. Converting to zero-based indexing simplifies modular arithmetic.

Implementation

def calculate_next_month(m: int) -> int:
    # Convert to 0-indexed (0-11)
    zero_based = m - 1
    # Apply modulo arithmetic
    next_zero = (zero_based + 1) % 12
    # Convert back to 1-indexed
    return next_zero + 1

String Capitalization Transformation

Problem Statement

Convert input string text such that:

• The initial character becomes uppercase
• All subsequent characters become lowercase

Solution Approach

Process the string in two distinct segments: the first character and the remaining portion.

Implementation

#include <cctype>
#include <string>

std::string transform_case(const std::string& input) {
    if (input.empty()) return "";
    
    std::string output;
    output.reserve(input.length());
    
    // Capitalize first character
    output.push_back(std::toupper(input[0]));
    
    // Convert remaining to lowercase
    for (size_t pos = 1; pos < input.length(); ++pos) {
        output.push_back(std::tolower(input[pos]));
    }
    
    return output;
}

Constrained Subtraction Game

Problem Statement

Starting from integer start_value, repeatedly subtract 1, 2, or 3. Avoid three forbidden values blocked_a, blocked_b, blocked_c. Determine if reaching exactly 0 is posible within 100 moves.

Solution Approach

Breadth-first search explores reachable values while tracking operation count. Forbidden values are filtered during traversal.

Implementation

#include <queue>
#include <unordered_set>
#include <algorithm>

bool can_reach_zero(int start_value, int blocked_a, int blocked_b, int blocked_c) {
    std::unordered_set<int> forbidden = {blocked_a, blocked_b, blocked_c};
    std::queue<std::pair<int, int>> exploration_queue;
    std::unordered_set<int> discovered;
    
    exploration_queue.push({start_value, 0});
    discovered.insert(start_value);
    
    while (!exploration_queue.empty()) {
        auto [current, move_count] = exploration_queue.front();
        exploration_queue.pop();
        
        if (current == 0) return true;
        if (move_count >= 100) continue;
        
        for (int step_size : {1, 2, 3}) {
            int next_value = current - step_size;
            if (next_value < 0) continue;
            if (forbidden.count(next_value) > 0) continue;
            if (discovered.count(next_value) > 0) continue;
            
            discovered.insert(next_value);
            exploration_queue.push({next_value, move_count + 1});
        }
    }
    
    return false;
}

Random Walk Probability Calculation

Problem Statement

From origin (0,0), perform exactly total_jumps jumps of length jump_dist in cardinal directions. Each direction has equal probability. Calcluate the probability of reaching target coordinates (target_x, target_y).

Constraints

-10⁹ ≤ target_x, target_y ≤ 10⁹, total_jumps ≤ 1000

Mathematical Framework

Normalization: Target coordinates must be divisible by jump_dist. Scale down: tx = |target_x| / jump_dist, ty = |target_y| / jump_dist.

Feasibility: If tx + ty > total_jumps, probability is zero.

Symmetry: Equal probabilities for opposite directions allow using absolute values.

Combinatorial Derivation

For k horizontal jumps:

• Right jumps: (k + tx) / 2
• Left jumps: (k - tx) / 2

For total_jumps - k vertical jumps:

• Up jumps: (total_jumps - k + ty) / 2
• Down jumps: (total_jumps - k - ty) / 2

Probability formula:

Σ [C(total_jumps, k) × C(k, (k+tx)/2) × C(total_jumps-k, (total_jumps-k+ty)/2)] / 4^total_jumps

Efficient Computation

Compute normalized binomial coefficients binom[n][k] = C(n,k) / 2^n:

binom[0][0] = 1
binom[i][0] = binom[i][i] = binom[i-1][0] / 2
binom[i][j] = (binom[i-1][j-1] + binom[i-1][j]) / 2

Final probability simplifies to:

Σ binom[total_jumps][k] × binom[k][(k+tx)/2] × binom[total_jumps-k][(total_jumps-k+ty)/2]

Implementation

#include <vector>
#include <cmath>
#include <iomanip>

using long_double = long double;

long_double calculate_probability(int total_jumps, int jump_dist, 
                                   int target_x, int target_y) {
    target_x = std::abs(target_x);
    target_y = std::abs(target_y);
    
    if (target_x % jump_dist != 0 || target_y % jump_dist != 0) return 0.0L;
    
    int tx = target_x / jump_dist;
    int ty = target_y / jump_dist;
    
    if (tx + ty > total_jumps) return 0.0L;
    
    std::vector<std::vector<long_double>> binom(total_jumps + 1, 
                                                std::vector<long_double>(total_jumps + 1, 0));
    binom[0][0] = 1.0L;
    
    for (int n = 1; n <= total_jumps; ++n) {
        binom[n][0] = binom[n][n] = binom[n-1][0] / 2.0L;
        for (int k = 1; k < n; ++k) {
            binom[n][k] = (binom[n-1][k-1] + binom[n-1][k]) / 2.0L;
        }
    }
    
    auto is_valid_integer = [](int value) {
        return value >= 0 && (value % 2 == 0);
    };
    
    long_double result = 0.0L;
    
    for (int k = 0; k <= total_jumps; ++k) {
        int right_jumps = (k + tx) / 2;
        int left_jumps = (k - tx) / 2;
        int up_jumps = (total_jumps - k + ty) / 2;
        int down_jumps = (total_jumps - k - ty) / 2;
        
        if (is_valid_integer(k + tx) && is_valid_integer(k - tx) &&
            is_valid_integer(total_jumps - k + ty) && is_valid_integer(total_jumps - k - ty) &&
            right_jumps >= 0 && left_jumps >= 0 && up_jumps >= 0 && down_jumps >= 0) {
            
            result += binom[total_jumps][k] * 
                     binom[k][right_jumps] * 
                     binom[total_jumps - k][up_jumps];
        }
    }
    
    return result;
}