A. Cloudberry Jam

Cloudberries and sugar are mixed in equal weight to make jam. During cooking, 25% of the total mixture evaporates. For each 2 kg of cloudberries, you get 3 kg of jam. You need to fill n jars, each holding 3 kg of jam. Determine the required kilograms of cloudberries (n ≤ 108).

Solution: Since every 2 kg of berreis yields 3 kg of jam, the answer is simply n × 2.

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int t;
    cin >> t;
    while (t--) {
        long long n;
        cin >> n;
        cout << (n << 1) << "\n";
    }
    return 0;
}

B. Large Array and Segments

Given an array a of n positive integers and a positive integer k, construct array b by repeating a exactly k times. For a given threshold x, count indices l (1 ≤ l ≤ n·k) such that there exists r ≥ l with the sum of b[l…r] ≥ x. Constraints: n,k ≤ 105, x ≤ 1018.

Solution: The valid l form a prefix of positions. Iterate over whole cycles; if the remaining suffix sum of the current cycle is already enough for all positions in the cycle, add n. Otherwise, check each position individually and break because later cycles cannot contribute.

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int t;
    cin >> t;
    while (t--) {
        int n, k;
        ll x;
        cin >> n >> k >> x;
        vector<int> a(n);
        for (auto &v : a) cin >> v;
        ll total = accumulate(a.begin(), a.end(), 0LL);
        ll remaining = total * k;
        ll ans = 0;
        for (int i = 0; i < k; ++i) {
            // check if the whole current block works
            if (remaining - total + a.back() >= x) {
                ans += n;
            } else {
                for (int j = 0; j < n; ++j) {
                    if (remaining >= x) ++ans;
                    remaining -= a[j];
                }
                break;
            }
            remaining -= total;
        }
        cout << ans << "\n";
    }
    return 0;
}

C. Disappearing Permutation

You are given a permutation p of size n. Process n queries; in the i-th query replace p[di] by 0 (each position is replaced exactly once, changes are cumulative). After each query, find the minimum number of operations to turn the current array into any permutation of [1…n]. A operation consists of choosing i and setting arr[i] = i. n ≤ 105.

Solution: Build a directed graph where each i points to p[i]. The graph consists of cycles. When a position is zeroed, its target (p[i]) becomes required. For each cycle, if at least one node is zeroed, all nodes in that cycle must be fixed. Use DFS to count cumulative required nodes as zeros appear.

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int t;
    cin >> t;
    while (t--) {
        int n;
        cin >> n;
        vector<int> p(n), d(n);
        for (auto &v : p) { cin >> v; --v; }
        for (auto &v : d) { cin >> v; --v; }
        vector<bool> visited(n, false);
        int current = 0;
        for (int i = 0; i < n; ++i) {
            int u = d[i];
            if (!visited[u]) {
                // traverse cycle from u
                int v = u;
                while (!visited[v]) {
                    visited[v] = true;
                    ++current;
                    v = p[v];
                }
            }
            cout << current << " \n"[i == n-1];
        }
    }
    return 0;
}

D. Even String

Construct a string of lowercase letters where for any equal letters at positions i and j, |i−j| is even. You are given an array c of length 26: the required count of each letter. Count distinct strings satisfying the parity condition, modulo 998244353. Total sum of c ≤ 5·105.

Solution: The condition forces each letter to occupy only odd positions or only even positions. Let odd = ⌈total/2⌉, even = total/2. After deciding which letters go to odd positions, the number of strings is (odd!·even!)/∏ci!. Compute the number of valid assignments of letters to odd/even via DP (subset sum). Multiply by the factorial quotient.

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

ll modpow(ll a, ll e) {
    ll res = 1;
    while (e) {
        if (e & 1) res = res * a % MOD;
        a = a * a % MOD;
        e >>= 1;
    }
    return res;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    const int MAX = 8000000;
    vector<ll> fact(MAX + 1), invfact(MAX + 1);
    fact[0] = 1;
    for (int i = 1; i <= MAX; ++i) fact[i] = fact[i-1] * i % MOD;
    invfact[MAX] = modpow(fact[MAX], MOD-2);
    for (int i = MAX; i >= 1; --i) invfact[i-1] = invfact[i] * i % MOD;

    int t;
    cin >> t;
    while (t--) {
        vector<int> c(26);
        int total = 0;
        for (auto &x : c) { cin >> x; total += x; }
        int odd = (total + 1) / 2, even = total / 2;
        ll base = fact[odd] * fact[even] % MOD;
        for (int x : c) base = base * invfact[x] % MOD;
        // DP subset sum for odd positions
        vector<ll> dp(odd + 1, 0);
        dp[0] = 1;
        for (int x : c) {
            if (x == 0) continue;
            for (int j = odd; j >= x; --j)
                dp[j] = (dp[j] + dp[j - x]) % MOD;
        }
        ll ans = dp[odd] * base % MOD;
        cout << ans << "\n";
    }
    return 0;
}