Given a completed 9×9 Sudoku grid, the task requires preserving some digits (minimum one) while replacing others with mines. The condition is that each remaining digit must equal the count of adjacent mines in its 8 surrounding cells.

Solution Approach

Identify any non-edge cell containing '8' and convert all other cells to mines. This satisfies the condition since an '8' must be surrounded by exactly 8 mines.

Implementation

#include <iostream>
#include <vector>

int main() {
    std::vector<std::string> grid(9);
    for (auto &row : grid) std::cin >> row;

    for (int i = 1; i < 8; i++) {
        for (int j = 1; j < 8; j++) {
            if (grid[i][j] == '8') {
                grid.assign(9, std::string(9, '*'));
                grid[i][j] = '8';
                for (const auto &row : grid) std::cout << row << '\n';
                return 0;
            }
        }
    }
    return 0;
}

Optimal Value Reduction Problem

Given n operations where each transforms x to |x - a_i|, find the minimal value achievable starting from D.

Mathematical Insight

Using Bézout's identity, the solution reduces to finding the greatest common divisor (GCD) of all a_i values. The minimal result is min(D mod g, g - D mod g) where g is the GCD.

Implementation

#include <iostream>
#include <numeric>

int main() {
    long long n, D, g = 0;
    std::cin >> n >> D;
    
    while (n--) {
        long long h;
        std::cin >> h;
        g = std::gcd(h, g);
    }
    
    std::cout << std::min(g - D % g, D % g);
    return 0;
}

River Crossing Optimizaton

Transport n people across a river using a boat with capacity betweeen L and R. Each person has stamina h_i determining how many extra trips they can make.

Key Calculation

The solution involves calculating minimum return trips S = ⌈(n-R)/(R-L)⌉ and verifying if the total available stamina Σmin(⌊(h_i-1)/2⌋, S) ≥ S×L.

Implementation

#include <iostream>
#include <cmath>

int main() {
    int n, l, r;
    std::cin >> n >> l >> r;
    
    long long S = std::ceil(1.0 * (n - r) / (r - l));
    long long total = 0;
    
    while (n--) {
        int h;
        std::cin >> h;
        total += std::min(S, (long long)(h - 1) / 2);
    }
    
    std::cout << (total >= S * l ? "Yes" : "No");
    return 0;
}

Game Outcome Prediction

Predict match winners based on cyclic score patterns, where a match requires 2a-1 games to win a set and 2b-1 sets to win the match.

Algorithm

Use binary lifting to precompute jump positions and score sums, then determine the winner by accumulating scores through the jumps.

Implementation

#include <iostream>
#include <vector>

int main() {
    int n, a, b;
    std::cin >> n >> a >> b;
    
    std::vector<std::vector<int>> jump(18, std::vector<int>(n));
    std::vector<std::vector<int>> sum(18, std::vector<int>(n));
    
    std::string s;
    std::cin >> s;
    
    int scores[2] = {}, pos = 0;
    for (int i = 0; i < n; i++) {
        while (scores[0] < a && scores[1] < a) {
            scores[s[pos] - '0']++;
            pos = (pos + 1) % n;
        }
        jump[0][i] = pos;
        sum[0][i] = scores[1] > scores[0];
        scores[s[i] - '0']--;
    }
    
    for (int i = 1; i < 18; i++) {
        for (int j = 0; j < n; j++) {
            jump[i][j] = jump[i-1][jump[i-1][j]];
            sum[i][j] = sum[i-1][j] + sum[i-1][jump[i-1][j]];
        }
    }
    
    for (int i = 0; i < n; i++) {
        int current = i, result = 0, wins = 0;
        for (int j = 17; j >= 0; j--) {
            if (result + (1 << j) <= 2*b-1) {
                result += 1 << j;
                wins += sum[j][current];
                current = jump[j][current];
            }
        }
        std::cout << (wins >= b);
    }
    return 0;
}

Domino Arrangement Puzzle

Arrange n dominoes with numbers (x_i, y_i) in a row ensuring adjacent numbers from different dominoes are distinct.

Strategy

Handle pairs where x ≠ y by checking previous placements, and manage identical pairs (x = y) by either separating them or inserting in gaps.

Implementation

#include <iostream>
#include <vector>

int main() {
    int n;
    std::cin >> n;
    
    int special_val = 0, count = 0;
    std::vector<int> first, second;
    
    for (int i = 0; i < n; i++) {
        int x, y;
        std::cin >> x >> y;
        
        if (x != y) {
            if (!second.empty() && second.back() == x) {
                first.push_back(y);
                second.push_back(x);
            } else {
                first.push_back(x);
                second.push_back(y);
            }
        } else {
            if (!count || special_val == x) {
                special_val = x;
                count++;
            } else {
                if (second.empty() || second.back() == x) {
                    first.push_back(special_val);
                    second.push_back(special_val);
                    first.push_back(x);
                    second.push_back(x);
                } else {
                    first.push_back(x);
                    second.push_back(x);
                    first.push_back(special_val);
                    second.push_back(special_val);
                }
                count--;
            }
        }
    }
    
    std::vector<std::pair<int, int>> result;
    for (int i = 0; i < first.size(); i++) {
        if (count && i && first[i] != second[i-1] && first[i] != special_val && second[i-1] != special_val) {
            result.emplace_back(special_val, special_val);
            count--;
        }
        if (count && !i && first[i] != special_val) {
            result.emplace_back(special_val, special_val);
            count--;
        }
        result.emplace_back(first[i], second[i]);
    }
    
    if (count && (second.empty() || second.back() != special_val)) {
        result.emplace_back(special_val, special_val);
        count--;
    }
    
    if (count) {
        std::cout << "No\n";
    } else {
        std::cout << "Yes\n";
        for (const auto &p : result) {
            std::cout << p.first << ' ' << p.second << '\n';
        }
    }
    return 0;
}