F-Tourist

Iterate through the input array while tracking the cumulative score. Once the threshold of 4000 is reached, output the current one-based index and terminate early.

#include <iostream>
#include <vector>

using namespace std;

void solve() {
    int n;
    cin >> n;
    vector<int> scores(n);
    int target_threshold = 4000;
    
    for (int i = 0; i < n; ++i) {
        cin >> scores[i];
        if (scores[i] >= target_threshold) {
            cout << (i + 1) << "\n";
            return;
        }
    }
}

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

J-Stacking of Goods

A greedy optimization problem. To minimize the total compressed volume impact, adjacent items should be ordered based on the comparison of their compression factors and widths. For any two items A and B, placing A below B yields less overhead than B below A when A.factor * B.width < B.factor * A.width. After sorting, simulate the stacking process by accumulating the load and calculating the net volume reduction.

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

using namespace std;
using ll = long long;

struct Product {
    ll width, height, compressionFactor;
};

void solve() {
    int n;
    cin >> n;
    vector<Product> items(n);
    
    for (int i = 0; i < n; ++i) {
        cin >> items[i].width >> items[i].height >> items[i].compressionFactor;
    }

    sort(items.begin(), items.end(), [](const Product& a, const Product& b) {
        return a.compressionFactor * b.width < b.compressionFactor * a.width;
    });

    ll totalVolumeReduction = 0;
    ll currentLoad = 0;
    
    for (const auto& item : items) {
        totalVolumeReduction += item.height - item.compressionFactor * currentLoad;
        currentLoad += item.width;
    }
    cout << totalVolumeReduction << "\n";
}

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

I-Strange Binary

This problem requires constructing a sequence of coefficients satisfying binary decomposition rules without consecutive zeros. Extract the base-2 representation of n into an array. If n % 4 == 0, the constraints cannot be satisfied. Otherwise, scan the coefficient array for adjacent zero pairs. When found, replace the first zero with -1 and copy the preceding value into the second position to break the consecutive zero pattern. Output the resulting array in a formatted grid.

#include <iostream>
#include <vector>

using namespace std;
using ll = long long;

void solve() {
    ll n;
    cin >> n;

    if (n % 4 == 0) {
        cout << "NO\n";
        return;
    }

    cout << "YES\n";
    vector<ll> coeffs(32);
    
    for (int i = 0; i < 32; ++i) {
        coeffs[i] = n & 1;
        n >>= 1;
    }

    for (int i = 1; i < 31; ++i) {
        if (coeffs[i] == 0 && coeffs[i + 1] == 0) {
            coeffs[i] = coeffs[i - 1];
            coeffs[i - 1] *= -1;
        }
    }

    for (int row = 0; row < 4; ++row) {
        for (int col = 0; col < 8; ++col) {
            cout << coeffs[row * 8 + col] << (col == 7 ? "" : " ");
        }
        cout << "\n";
    }
}

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

L-502 Bad Gateway

Derive the expected value function based on a critical decision point a. The expectation formula simplifies to a rational function where the optimal a occurs near sqrt(2T). Evaluate the expectation at both floor(sqrt(2T)) and ceil(sqrt(2T)), then compare the resulting fractions using cross-multiplication to avoid floating-point inaccuracies. Output the fraction reduced to its lowest terms via greatest common divisor.

#include <iostream>
#include <cmath>
#include <algorithm>

using namespace std;
using ll = long long;

ll gcd_func(ll a, ll b) {
    while (b) {
        a %= b;
        swap(a, b);
    }
    return a;
}

void solve() {
    ll n;
    cin >> n;
    if (n == 1) {
        cout << "1 1\n";
        return;
    }

    ll threshold = static_cast<ll>(sqrt(2.0 * n));
    
    auto evaluate = [&](ll a) -> pair<ll, ll> {
        ll num = a * a + 2 * n - a;
        ll den = 2 * a;
        ll g = gcd_func(num, den);
        return {num / g, den / g};
    };

    auto [num1, den1] = evaluate(threshold);
    auto [num2, den2] = evaluate(threshold + 1);

    if ((__int128)num1 * den2 > (__int128)num2 * den1) {
        cout << num2 << " " << den2 << "\n";
    } else {
        cout << num1 << " " << den1 << "\n";
    }
}

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

G-Game

Simulate a probabilistic game following Euclidean division steps. Alice and Bob alternate turns based on quotient magnitudes. Maintain running probabilities and accumulate Alice's expected reward using modular geometric series summation. Handle edge cases where probabilities equal 1 to prevent division by zero. Iterate until one variable reaches zero, then combine the accumulated expectation with the remaining probability factor.

#include <iostream>
#include <numeric>

using namespace std;
using ll = long long;

const ll MOD = 998244353;

ll mod_pow(ll base, ll exp) {
    ll res = 1;
    base %= MOD;
    while (exp > 0) {
        if (exp & 1) res = res * base % MOD;
        base = base * base % MOD;
        exp >>= 1;
    }
    return res;
}

ll mod_inv(ll n) {
    return mod_pow(n, MOD - 2);
}

void solve() {
    ll x, y;
    cin >> x >> y;
    ll p_a, p_b, q;
    cin >> p_a >> p_b >> q;

    ll val = (p_a + p_b) % MOD;
    ll inv_val = mod_inv(val);
    ll prob_a = p_a * inv_val % MOD;
    ll prob_b = p_b * inv_val % MOD;

    ll alice_expected = 0;
    ll current_prob_factor = 1;
    bool a_zero = (p_a == 0);

    ll u = x, v = y;
    while (u > 0 && v > 0) {
        if (a_zero) {
            if (u >= v) u %= v;
            else {
                current_prob_factor = 0;
                break;
            }
        } else {
            if (u >= v) {
                ll k = u / v;
                ll r = mod_pow(prob_b, k);
                
                ll term_sum = 0;
                if (prob_b != 1) {
                    ll denom = (1 - prob_b + MOD) % MOD;
                    ll geom_num = (1 - r + MOD) % MOD;
                    term_sum = prob_a * geom_num % MOD * mod_inv(denom) % MOD;
                } else {
                    term_sum = prob_a * k % MOD;
                }

                alice_expected = (alice_expected + current_prob_factor * term_sum) % MOD;
                current_prob_factor = current_prob_factor * r % MOD;
                u %= v;
            } else {
                ll k = v / u;
                ll f = mod_pow(prob_a, k);
                current_prob_factor = current_prob_factor * f % MOD;
                v %= u;
            }
        }
    }

    ll finish_flag = (v == 0) ? 1 : 0;
    ll ans = (alice_expected + current_prob_factor * finish_flag) % MOD;
    if (ans < 0) ans += MOD;
    cout << ans << "\n";
}

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

A-Gambling on Choosing Regionals

Calculate team rankings by evaluating how many university squads possess sufficient higher-skilled members relative to a dynamic threshold. Precompute school membership counts and establish a baseline rank contribution. Sort teams by skill level ascending, then iterate while temporarily removing each team from its school's count to measure the adjusted ranking under a reduced quota. Store results and permanently decrement the school count to maintain correctness for subsequent iterations in the sorted pass.

#include <iostream>
#include <vector>
#include <string>
#include <map>
#include <algorithm>

using namespace std;
using ll = long long;

struct TeamInfo {
    int originalIndex;
    ll skillLevel;
    string university;
};

void solve() {
    int n, k;
    cin >> n >> k;
    
    ll minThreshold = -1;
    for (int i = 0; i < k; ++i) {
        ll val;
        cin >> val;
        if (minThreshold == -1 || val < minThreshold) minThreshold = val;
    }

    vector<TeamInfo> teams(n);
    map<string, int> schoolCounts;
    vector<int> ranks(n);

    for (int i = 0; i < n; ++i) {
        ll val;
        cin >> val;
        string uni;
        cin >> uni;
        teams[i] = {i, val, uni};
        schoolCounts[uni]++;
    }

    ll baseCount = 0;
    for (auto const& [school, cnt] : schoolCounts) {
        baseCount += min(minThreshold, (ll)cnt);
    }

    sort(teams.begin(), teams.end(), [](const TeamInfo& a, const TeamInfo& b) {
        return a.skillLevel < b.skillLevel;
    });

    for (int i = 0; i < n; ++i) {
        int curCnt = schoolCounts[teams[i].university];
        baseCount -= min((ll)curCnt, minThreshold);
        
        int reducedCnt = curCnt - 1;
        ll adjustedRank = baseCount + min((ll)reducedCnt, minThreshold - 1);
        
        baseCount += min((ll)curCnt, minThreshold);
        ranks[teams[i].originalIndex] = adjustedRank + 1;
        
        schoolCounts[teams[i].university]--;
    }

    for (int i = 0; i < n; ++i) {
        cout << ranks[i] << "\n";
    }
}

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