A. Cosmic End

Find a number within a given range that is the product of three distinct primes.

Given the small constraitn (upper bound ≤ 100), precompute small primes and check all combinations of three distinct ones. The maximum third prime needed is around 100/(2×3) ≈ 16, so checking primes up to 19 suffices.

#include <bits/stdc++.h>
using namespace std;

int main() {
    int l, r;
    cin >> l >> r;
    vector<int> primes = {2, 3, 5, 7, 11, 13, 17, 19};
    for (int i = 0; i < primes.size(); ++i)
        for (int j = i + 1; j < primes.size(); ++j)
            for (int k = j + 1; k < primes.size(); ++k) {
                long long prod = 1LL * primes[i] * primes[j] * primes[k];
                if (l <= prod && prod <= r) {
                    cout << prod;
                    return 0;
                }
            }
    cout << -1;
}

B. Entangled Feelings

Given arrays a and b, minimize the minimum absolute difference between any pair |a_i - b_j| after permuting a. Output one such permutation.

Sort a. For each b_j, find the closest value in a via binary search. Track the global best pair. Swap those two elements in a and output.

#include <bits/stdc++.h>
using namespace std;

const int N = 1e5 + 10;
int a[N], b[N];

int main() {
    int n;
    cin >> n;
    for (int i = 0; i < n; ++i) cin >> a[i];
    for (int i = 0; i < n; ++i) cin >> b[i];
    if (n == 1) {
        cout << a[0];
        return 0;
    }
    sort(a, a + n);
    int best_diff = INT_MAX, pos_a = 0, pos_b = 0;
    for (int i = 0; i < n; ++i) {
        int idx = lower_bound(a, a + n, b[i]) - a;
        vector<int> candidates;
        if (idx < n) candidates.push_back(idx);
        if (idx > 0) candidates.push_back(idx - 1);
        if (idx + 1 < n) candidates.push_back(idx + 1);
        for (int j : candidates) {
            int diff = abs(a[j] - b[i]);
            if (diff < best_diff) {
                best_diff = diff;
                pos_a = j;
                pos_b = i;
            }
        }
    }
    swap(a[pos_b], a[pos_a]);
    for (int i = 0; i < n; ++i) cout << a[i] << " ";
}

C. Anatomy of Emotion

Represent a positive integer as the sum of three Fibonacci numbers (repetition allowed).

Precompute Fibonacci numbers up to ~1e9 (≈48 terms). Use triple nested loops or optimized two-pointer on sorted list to find a valid triplet.

#include <bits/stdc++.h>
using namespace std;

long long fib[50];

void init() {
    fib[0] = 0; fib[1] = 1;
    for (int i = 2; i < 50; ++i)
        fib[i] = fib[i-1] + fib[i-2];
}

void solve() {
    int x; cin >> x;
    for (int i = 0; i < 50; ++i)
        for (int j = i; j < 50; ++j)
            for (int k = j; k < 50; ++k)
                if (fib[i] + fib[j] + fib[k] == x) {
                    cout << fib[i] << " " << fib[j] << " " << fib[k] << "\n";
                    return;
                }
    cout << "-1\n";
}

int main() {
    init();
    int t; cin >> t;
    while (t--) solve();
}

D. Friendship Strategy

Compute probability of a "reverse sweep" (lose first two, win next three) in a best-of-five match where win probability per game is p.

The required sequence is LLWW?, but since match ends at 3 wins, only first four games matter: lose first two, win next two. Probability = (1-p)^2 * p^2.

#include <bits/stdc++.h>
using namespace std;

int main() {
    double p; cin >> p;
    printf("%.8f", (1-p)*(1-p)*p*p);
}

E. Future Prophecy

Simulate a race to (n+1)/2 wins. Given a string of outcomes ('R' or 'P'), determine winner and total games played.

Count wins incrementally. Stop when either reaches threshold. If neither does, output continuation status.

#include <bits/stdc++.h>
using namespace std;

int main() {
    char c; int n;
    cin >> c >> c >> n;
    string s; cin >> s;
    int r = 0, p = 0, target = (n + 1) / 2;
    for (int i = 0; i < s.size(); ++i) {
        if (s[i] == 'R') r++;
        else p++;
        if (r == target) {
            cout << "kou!\n" << i + 1;
            return 0;
        }
        if (p == target) {
            cout << "yukari!\n" << i + 1;
            return 0;
        }
    }
    cout << "to be continued.\n" << s.size();
}

G. Life's Ups and Downs

Consturct an array of length n, sum S, with exactly k "V-triplets" (pattern a, b, a with a > b).

Base pattern: repeat [x, 1] k times, then append x. This gives k V-triplets using 2k+1 elements. Fill remaining positions with 1s. Distribute leftover sum by increasing x or adjusting 1s carefully to avoid creating extra V-triplets.

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int T; cin >> T;
    while (T--) {
        ll n, S, k; cin >> n >> S >> k;
        if (n == 1) {
            cout << (k ? -1 : S) << '\n';
            continue;
        }
        if (n == 2) {
            cout << (k ? -1 : "1 " + to_string(S-1)) << '\n';
            continue;
        }
        if (k == 0) {
            for (int i = 0; i < n - 1; ++i) cout << "1 ";
            cout << S - n + 1 << '\n';
            continue;
        }
        if (n < 2 * k + 1 || S < n + k) {
            cout << "-1\n";
            continue;
        }
        ll base = (S - (n - (k + 1))) / (k + 1);
        vector<ll> ans;
        ll used = 0;
        for (int i = 0; i < k; ++i) {
            ans.push_back(base);
            ans.push_back(1);
            used += base + 1;
        }
        ans.push_back(base);
        used += base;
        ll rem = S - used;
        if (ans.size() < n) {
            while (ans.size() < n) {
                ans.push_back(1);
                rem--;
            }
            ans[ans.size() - 1] += rem;
        } else {
            ll inc = rem / (k + 1);
            for (int i = 0; i <= k; ++i) ans[2 * i] += inc;
            rem %= (k + 1);
            for (int i = 0; i < rem; ++i) ans[2 * i]++;
        }
        if (ans[0] <= ans[1]) {
            cout << "-1\n";
            continue;
        }
        for (int i = 0; i < n; ++i)
            cout << ans[i] << " \n"[i == n - 1];
    }
}

I. Interwoven Spacetime

Maximize sum of submatrix in a rank-1 matrix M[i][j] = a[i] * b[j].

Submatrix sum = (sum of subarray in a) × (sum of subarray in b). Compute max/min subarray sums for both arrays. Answer is max of all four products: maxA×maxB, maxA×minB, minA×maxB, minA×minB.

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

pair<ll, ll> getMinMax(vector<ll>& v) {
    ll max_ending = v[0], min_ending = v[0];
    ll max_so_far = v[0], min_so_far = v[0];
    for (int i = 1; i < v.size(); ++i) {
        max_ending = max(v[i], max_ending + v[i]);
        min_ending = min(v[i], min_ending + v[i]);
        max_so_far = max(max_so_far, max_ending);
        min_so_far = min(min_so_far, min_ending);
    }
    return {max_so_far, min_so_far};
}

int main() {
    int n, m; cin >> n >> m;
    vector<ll> a(n), b(m);
    for (auto& x : a) cin >> x;
    for (auto& x : b) cin >> x;
    auto [maxA, minA] = getMinMax(a);
    auto [maxB, minB] = getMinMax(b);
    ll ans = max({maxA * maxB, maxA * minB, minA * maxB, minA * minB});
    cout << ans;
}

J. Perfect Balance

Assign values 1 or 2 to nodes of a rooted tree so that every red-rooted subtree sums to a multiple of 3.

DFS post-order. Initially assign 1 to all. For each red node, compute sum of white descendants. If sum % 3 ≠ 0, adjust red node or one white child to fix modulo. If red node has no white children and sum % 3 ≠ 0, impossible.

#include <bits/stdc++.h>
using namespace std;

const int N = 1e5 + 10;
vector<int> g[N];
int val[N], subtree_sum[N];
char color[N];
bool possible = true;

void dfs_check(int u) {
    bool has_white = false;
    subtree_sum[u] = 1;
    for (int v : g[u]) {
        dfs_check(v);
        if (color[v] == 'W') {
            has_white = true;
            subtree_sum[u] += subtree_sum[v];
        }
    }
    if (color[u] == 'R' && !has_white && subtree_sum[u] % 3 != 0)
        possible = false;
}

void dfs_assign(int u) {
    for (int v : g[u]) dfs_assign(v);
    if (color[u] == 'R') {
        int rem = subtree_sum[u] % 3;
        if (rem == 1) {
            val[u] = 2;
            for (int v : g[u])
                if (color[v] == 'W') { val[v] = 2; break; }
        } else if (rem == 2) {
            val[u] = 2;
        }
    }
}

int main() {
    int n; cin >> n;
    cin >> (color + 1);
    for (int i = 1; i <= n; ++i) val[i] = 1;
    for (int i = 2; i <= n; ++i) {
        int p; cin >> p;
        g[p].push_back(i);
    }
    dfs_check(1);
    if (!possible) {
        cout << "-1";
        return 0;
    }
    dfs_assign(1);
    for (int i = 1; i <= n; ++i) cout << val[i];
}