A. Triangle Construction with Guaranteed Validity

Given four strictly increasing integers a < b < c < d, select three values x, y, z such that they form a non-degenerate triangle — i.e., satisfy the strict triangle inequality x + y > z. Since all inputs are ordered, the safest choice is to pick x = b, y = c, and z = c. This yields b + c > c, which simplifies to b > 0 — always true for positive integers. Thus, outputting b c c guarantees a valid triangle.

#include <iostream>
#include <vector>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int t;
    cin >> t;
    while (t--) {
        int a, b, c, d;
        cin >> a >> b >> c >> d;
        cout << b << ' ' << c << ' ' << c << '\n';
    }
    return 0;
}

B. Optimal Sequence of Dragon-Slaying Operations

A dragon has health x. Two operations are available: (1) replace x with ⌊x/2⌋ + 10, usable up to n times; (2) subtract 10, usable up to m times. To minimize final health, apply operation (1) greedily while x > 20 (since beyond this threshold, operation (1) strictly reduces x). After exhausting operation (1) or dropping below 21, apply operation (2) as needed. The dragon survives only if remaining health ≤ 10 × m.

#include <iostream>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int t;
    cin >> t;
    while (t--) {
        int x, n, m;
        cin >> x >> n >> m;
        while (x > 20 && n-- > 0) {
            x = x / 2 + 10;
        }
        cout << (x > 10 * m ? "NO" : "YES") << '\n';
    }
    return 0;
}

C. Maximizing Cultural Influence in a Tree Kingdom

In a rooted tree with n nodes (root = 1), choose exactly k nodes to mark as "industrial". Each unmarked node contributes its depth minus the number of industrial descendants (including itself) in its subtree. For each node u, define contribution[u] = depth[u] − size_of_industrial_subtree_rooted_at_u. Compute subtree sizes and depths via DFS. Sort nodes by contribution descending and sum the top k contributions.

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, k;
    cin >> n >> k;

    vector<vector<int>> graph(n + 1);
    for (int i = 1; i < n; ++i) {
        int u, v;
        cin >> u >> v;
        graph[u].push_back(v);
        graph[v].push_back(u);
    }

    vector<int> depth(n + 1), industrial_count(n + 1);
    
    function<void(int, int)> dfs = [&](int u, int parent) {
        depth[u] = depth[parent] + 1;
        industrial_count[u] = 1;
        for (int v : graph[u]) {
            if (v == parent) continue;
            dfs(v, u);
            industrial_count[u] += industrial_count[v];
        }
    };
    dfs(1, 0);

    vector<int> indices(n + 1);
    iota(indices.begin(), indices.end(), 0);
    sort(indices.begin() + 1, indices.end(), [&](int i, int j) {
        return depth[i] - industrial_count[i] > depth[j] - industrial_count[j];
    });

    long long total = 0;
    for (int i = 1; i <= k; ++i) {
        total += depth[indices[i]] - industrial_count[indices[i]];
    }
    cout << total << '\n';
    return 0;
}

D. Minimizing Squared Distance Among Three Sorted Arrays

Given three sorted arrays A, B, C, find a ∈ A, b ∈ B, c ∈ C minimizing (a−b)² + (a−c)² + (b−c)². Instead of brute-forcing all triple, fix one element (e.g., from A), then binary search near-optimal candidates in B and C around it. For each candidate a, examine at most 11 elements in B centered on the lower bound of a, and for each such b, examine up to 11 candidates in C near (a+b)/2. Repeat symmetrically for fixing B and C to cover all configurations.

#include <iiostream>
#include <vector>
#include <algorithm>
#include <climits>
#include <cmath>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int t;
    cin >> t;
    while (t--) {
        vector<int> sizes(3);
        for (int &s : sizes) cin >> s;

        vector<vector<int>> arr(3);
        for (int i = 0; i < 3; ++i) {
            arr[i].resize(sizes[i]);
            for (int &x : arr[i]) cin >> x;
            sort(arr[i].begin(), arr[i].end());
        }

        long long best = LLONG_MAX;
        auto update = [&](long long a, long long b, long long c) {
            long long diff = (a - b) * (a - b) + (a - c) * (a - c) + (b - c) * (b - c);
            best = min(best, diff);
        };

        for (int base = 0; base < 3; ++base) {
            const auto &X = arr[base];
            const auto &Y = arr[(base + 1) % 3];
            const auto &Z = arr[(base + 2) % 3];

            for (long long x : X) {
                auto y_it = lower_bound(Y.begin(), Y.end(), x);
                int start_y = max(0, (int)(y_it - Y.begin()) - 5);
                int end_y = min((int)Y.size(), (int)(y_it - Y.begin()) + 6);
                for (int iy = start_y; iy < end_y; ++iy) {
                    long long y = Y[iy];
                    long long mid_z = (x + y) / 2;
                    auto z_it = lower_bound(Z.begin(), Z.end(), mid_z);
                    int start_z = max(0, (int)(z_it - Z.begin()) - 5);
                    int end_z = min((int)Z.size(), (int)(z_it - Z.begin()) + 6);
                    for (int iz = start_z; iz < end_z; ++iz) {
                        update(x, y, Z[iz]);
                    }
                }
            }
        }
        cout << best << '\n';
    }
    return 0;
}

E. Counting Valid Magic Spell Constructions

Given strings S (length n) and T (length m), count ways to build a string matching T's prefix of length m using characters from S in order. At step i, you may prepend or append S[i] to the current string. Let dp[l][r] denote the number of ways to construct substring T[l..r] using the first r−l+1 characters of S. Base case: if S[0] matches T[i] (or i > m), set dp[i][i] = 2. Transition: if S[len−1] matches T[l] or l > m, add dp[l+1][r]; similarly for T[r]. Answer is sum of dp[1][j] for all j ≥ m, computed modulo 998244353.

#include <iostream>
#include <vector>
#include <string>
using namespace std;

constexpr int MOD = 998244353;

struct Mint {
    long long x;
    Mint(long long x = 0) : x((x % MOD + MOD) % MOD) {}
    Mint operator+(Mint o) const { return x + o.x >= MOD ? x + o.x - MOD : x + o.x; }
    Mint operator*(Mint o) const { return x * o.x % MOD; }
    Mint &operator+=(Mint o) { return *this = *this + o; }
    Mint &operator*=(Mint o) { return *this = *this * o; }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    string s, t;
    cin >> s >> t;
    int n = s.size(), m = t.size();

    vector<vector<Mint>> dp(n + 1, vector<Mint>(n + 1));
    s = " " + s, t = " " + t;

    for (int i = 1; i <= n; ++i) {
        if (i > m || s[1] == t[i]) {
            dp[i][i] = Mint(2);
        }
    }

    for (int len = 2; len <= n; ++len) {
        for (int l = 1; l + len - 1 <= n; ++l) {
            int r = l + len - 1;
            if (l > m || s[len] == t[l]) {
                dp[l][r] += dp[l + 1][r];
            }
            if (r > m || s[len] == t[r]) {
                dp[l][r] += dp[l][r - 1];
            }
        }
    }

    Mint ans;
    for (int r = m; r <= n; ++r) {
        ans += dp[1][r];
    }
    cout << ans.x << '\n';
    return 0;
}