Problem A: Rope Cutting Condition

The task requires determining how many ropes must be severed based on their attachment points. Each rope connects a nail at height a to a branch at height b. A cut is mandatory whenever the nail is positioned strictly higher than the branch. The algorithm iterates through all given pairs, evaluates this inequality, and accumulates the total number of required cuts.

#include <iostream>
#include <vector>

void process_case() {
    int n;
    std::cin >> n;
    int cuts = 0;
    for (int i = 0; i < n; ++i) {
        int nail_h, branch_h;
        std::cin >> nail_h >> branch_h;
        if (nail_h > branch_h) {
            ++cuts;
        }
    }
    std::cout << cuts << '\n';
}

int main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(nullptr);
    int t;
    std::cin >> t;
    while (t--) {
        process_case();
    }
    return 0;
}

Problem B: Tic-Tac-Toe State Evaluation

Given a completed or partially filled 3x3 grid, the goal is to identify if either player has achieved a winning line. The solution scans all three rows, three columns, and two diagonals. If any line contains three identical non-empty characters, that character is declared the winner. If no winning configuration exists after checking all eight possibilities, the match is classified as a draw.

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

char evaluate_board(const std::vector<std::string>& grid) {
    for (int i = 0; i < 3; ++i) {
        if (grid[i][0] != '.' && grid[i][0] == grid[i][1] && grid[i][1] == grid[i][2])
            return grid[i][0];
        if (grid[0][i] != '.' && grid[0][i] == grid[1][i] && grid[1][i] == grid[2][i])
            return grid[0][i];
    }
    if (grid[1][1] != '.') {
        if (grid[0][0] == grid[1][1] && grid[1][1] == grid[2][2]) return grid[1][1];
        if (grid[0][2] == grid[1][1] && grid[1][1] == grid[2][0]) return grid[1][1];
    }
    return 'D';
}

void solve() {
    std::vector<std::string> board(3);
    for (auto& row : board) std::cin >> row;
    char result = evaluate_board(board);
    if (result == 'D') std::cout << "DRAW\n";
    else std::cout << result << '\n';
}

int main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(nullptr);
    int t; std::cin >> t;
    while (t--) solve();
    return 0;
}

Problem C: Competition Ranking Strategy

Participants solve problems with varying time costs within a fixed duration limit. To minimize penalty and maximize solved count, each participant should greedily attempt problems in ascending order of required time. After computing the solved count and cumulative penalty for every contestant, the participants are sorted primarily by problems solved (descending) and secondarily by penalty (ascending). The final step locates the 1-based rank of the first participant in this sorted sequence.

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

struct Participant {
    int id;
    int solved_cnt;
    long long total_penalty;
};

void solve() {
    int n, m, limit;
    std::cin >> n >> m >> limit;
    std::vector<Participant> contestants(n);

    for (int i = 0; i < n; ++i) {
        std::vector<int> durations(m);
        for (int& d : durations) std::cin >> d;
        std::sort(durations.begin(), durations.end());

        int elapsed = 0;
        long long penalty = 0;
        int solved = 0;

        for (int d : durations) {
            if (elapsed + d > limit) break;
            elapsed += d;
            penalty += elapsed;
            ++solved;
        }
        contestants[i] = {i + 1, solved, penalty};
    }

    std::sort(contestants.begin(), contestants.end(), [](const Participant& a, const Participant& b) {
        if (a.solved_cnt != b.solved_cnt) return a.solved_cnt > b.solved_cnt;
        return a.total_penalty < b.total_penalty;
    });

    for (int rank = 0; rank < n; ++rank) {
        if (contestants[rank].id == 1) {
            std::cout << rank + 1 << '\n';
            return;
        }
    }
}

int main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(nullptr);
    int t; std::cin >> t;
    while (t--) solve();
    return 0;
}

Problem D: Crhistmas Tree Branch Area

This problem involves calculating the visible area of overlapping isosceles triangles placed at specific vertical coordinates. After sorting the branch heights in ascending order, each triangle's contribution is evaluated sequentially. If a triangle does not intersect with the one immediately above it, its full area is added. When an overlap occurs, the intersecting region forms a smaller similar triagnle at the top. Using geometric similarity ratios, the overlapping area is computed and subtracted from the full triangle area to determine the visible portion.

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

void solve() {
    int n;
    double base_width, tri_height;
    std::cin >> n >> base_width >> tri_height;
    std::vector<double> positions(n);
    for (double& p : positions) std::cin >> p;
    std::sort(positions.begin(), positions.end());

    double visible_area = 0.0;
    for (int i = 0; i < n; ++i) {
        double full = 0.5 * base_width * tri_height;
        if (i == n - 1 || positions[i] + tri_height <= positions[i + 1]) {
            visible_area += full;
        } else {
            double overlap_h = (positions[i] + tri_height) - positions[i + 1];
            double scale = overlap_h / tri_height;
            double overlap_base = base_width * scale;
            double overlap_area = 0.5 * overlap_base * overlap_h;
            visible_area += (full - overlap_area);
        }
    }
    std::cout << std::fixed << std::setprecision(7) << visible_area << '\n';
}

int main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(nullptr);
    int t; std::cin >> t;
    while (t--) solve();
    return 0;
}

Problem E: Snowflake Number Representation

The objective is to verify if a integer n can be expressed as a geometric series 1 + x + x^2 + ... + x^k where x > 1 and k > 1. The approach splits the problem based on the exponent k. For k >= 3, the base x cannot exceed 10^6 given the constraint n <= 10^18. All valid numbers for this range are precomputed and stored in a hash set. For the remaining case where k = 2, the equation reduces to x^2 + x + 1 = n. A binary search over possible values of x efficiently determines if an integer solution exists.

#include <iostream>
#include <unordered_set>
#include <vector>

std::unordered_set<long long> precomputed_vals;

void initialize() {
    const long long MAX_N = 1e18;
    for (long long base = 2; base <= 1000000; ++base) {
        long long current = 1 + base + base * base;
        long long term = base * base * base;
        while (current <= MAX_N) {
            precomputed_vals.insert(current);
            if (MAX_N - current < term) break;
            current += term;
            if (MAX_N / term < base) break;
            term *= base;
        }
    }
}

bool check_quadratic(long long target) {
    long long low = 2, high = 1000000000;
    while (low <= high) {
        long long mid = low + (high - low) / 2;
        long long val = mid * mid + mid + 1;
        if (val == target) return true;
        if (val < target) low = mid + 1;
        else high = mid - 1;
    }
    return false;
}

void solve() {
    long long n;
    std::cin >> n;
    if (precomputed_vals.count(n) || check_quadratic(n)) {
        std::cout << "YES\n";
    } else {
        std::cout << "NO\n";
    }
}

int main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(nullptr);
    initialize();
    int t; std::cin >> t;
    while (t--) solve();
    return 0;
}

Problem G: Symptom State Transitions

Health conditions are modeled as bitmasks of length n, where each bit represents the presence or absence of a specific symptom. Medicines act as directed edges in a graph, transitioning one state to another by clearing specified symptoms and introducing others, each with an associated cost. With n <= 10, the state space contains at most 1024 nodes. Dijkstra's algorithm is applied to find the minimum cumulative cost to transition from the initial symptom mask to the zero mask (completely healthy state).

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

struct Node {
    int mask;
    int dist;
    bool operator>(const Node& other) const {
        return dist > other.dist;
    }
};

struct Treatment {
    int cost;
    int clear_bits;
    int add_bits;
};

void solve() {
    int n, m;
    std::cin >> n >> m;
    std::string init_str;
    std::cin >> init_str;
    int start_mask = 0;
    for (int i = 0; i < n; ++i) {
        if (init_str[i] == '1') start_mask |= (1 << i);
    }

    std::vector<Treatment> meds(m);
    for (int i = 0; i < m; ++i) {
        std::string c_str, a_str;
        std::cin >> meds[i].cost >> c_str >> a_str;
        int c_mask = 0, a_mask = 0;
        for (int j = 0; j < n; ++j) {
            if (c_str[j] == '1') c_mask |= (1 << j);
            if (a_str[j] == '1') a_mask |= (1 << j);
        }
        meds[i].clear_bits = c_mask;
        meds[i].add_bits = a_mask;
    }

    int state_count = 1 << n;
    std::vector<int> min_dist(state_count, INT_MAX);
    std::priority_queue<Node, std::vector<Node>, std::greater<Node>> pq;

    min_dist[start_mask] = 0;
    pq.push({start_mask, 0});

    while (!pq.empty()) {
        Node curr = pq.top();
        pq.pop();

        if (curr.dist > min_dist[curr.mask]) continue;
        if (curr.mask == 0) {
            std::cout << curr.dist << '\n';
            return;
        }

        for (const auto& med : meds) {
            int next_state = (curr.mask & ~med.clear_bits) | med.add_bits;
            int next_cost = curr.dist + med.cost;
            if (next_cost < min_dist[next_state]) {
                min_dist[next_state] = next_cost;
                pq.push({next_state, next_cost});
            }
        }
    }
    std::cout << -1 << '\n';
}

int main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(nullptr);
    int t; std::cin >> t;
    while (t--) solve();
    return 0;
}