T1 Three Integers

Problem Statement

Given three integers A, B, and C, there are two operations:

• Operation 1: Choose two numbers and decrement each by 1.
• Operation 2: Choose all three numbers and decrement each by 1.

The goal is to reduce all three numbers to 0. If impossible, output -1.

Solution Approach

A key insight is that any operation should involve the largest number. If it doesn't, such as in Operation 1 applied to the two smallest numbers, it is suboptimal.

Consider sorting the numbers in non-decreasing order: let them be a ≤ b ≤ c. The condition for feasibility is that the sum of the two smallest numbers must be at least the largest: a + b ≥ c. If this holds, the minimum number of operations is c, as each operation reduces the largest number by at least 1, and the other numbers can be adjusted accordingly.

Code Implementation

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

int main() {
    long long A, B, C;
    cin >> A >> B >> C;
    long long arr[] = {A, B, C};
    sort(arr, arr + 3);
    if (arr[0] + arr[1] < arr[2]) {
        cout << -1 << endl;
    } else {
        cout << arr[2] << endl;
    }
    return 0;
}

T2 Counting Grids

Problem Statement

Fill an n × n grid with numbers from 1 to n² such that no cell is simultnaeously the minimum in its row and the maximum in its column. Count the number of valid arrangements.

Solution Approach

Use the principle of inclusion-exclusion. A "bad" cell is defined as one that is both the row minimum and column maximum. It can be proven that at most one bad cell exists in any arrangement, as two bad cells would lead to a contradiction.

Assume a specific cell is bad. Let the value in that cell be x. The number of ways to choose the remaining n-1 numbers for its row from the numbers greater than x is C(n² - x, n-1), and for its column from the numbers less than x is C(x-1, n-1). The row and column can be permuted independently, contributing (n-1)!². The remaining (n-1)² cells can be arranged arbitrarily, contributing ((n-1)²)!.

Summing over all possible x and accounting for the choice of the bad cell (n² possibilities), the total number of invalid arrangements is:

n² × ((n-1)!)² × ((n-1)²)! × Σ_{x=1}^{n²} C(n² - x, n-1) C(x-1, n-1)

Simplify to:

((n-1)²)! × (n!)² × Σ_{x=1}^{n²} C(n² - x, n-1) C(x-1, n-1)

The valid arrangements are the total permutations minus the invalid ones: (n²)! - invalid_count.

Precompute factorials and modular inverses for efficiency.

Code Implementation

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

const long long MOD = 998244353;
long long factorial[250005], inverse[250005];

long long power(long long base, long long exp) {
    long long result = 1;
    while (exp) {
        if (exp & 1) result = result * base % MOD;
        base = base * base % MOD;
        exp >>= 1;
    }
    return result;
}

long long comb(long long n, long long k) {
    if (k < 0 || k > n) return 0;
    return factorial[n] * inverse[n - k] % MOD * inverse[k] % MOD;
}

int main() {
    long long n;
    cin >> n;
    factorial[0] = inverse[0] = 1;
    for (int i = 1; i <= n * n; i++) {
        factorial[i] = factorial[i - 1] * i % MOD;
        inverse[i] = power(factorial[i], MOD - 2);
    }
    long long invalid = 0;
    long long factor = factorial[(n - 1) * (n - 1)] * factorial[n] % MOD * factorial[n] % MOD;
    for (int x = n; x <= n * n - n + 1; x++) {
        invalid = (invalid + factor * comb(n * n - x, n - 1) % MOD * comb(x - 1, n - 1)) % MOD;
    }
    long long total = factorial[n * n];
    long long answer = (total - invalid + MOD) % MOD;
    cout << answer << endl;
    return 0;
}

T3 Piles of Pebbles

Problem Statement

There are n piles of pebbles. Two players alternate turns. On a turn, a player selects at least one pile and removes X pebbles (if it's the first player) or Y pebbles (if it's the second player). The player who cannot make a move loses. Determine the winner assuming optimal play.

Solution Approach

Analyze the game by considering the residues of pile sizes modulo (X + Y). Define a position as winning if the current player can force a win, and losing otherwise.

For a single pile, the pattern repeats every (X + Y). Specifically:

• If the residue is in [0, X-1], it is a losing position for the first player.
• Otherwise, it is a winning position for the first player.

For multiple piles, the outcome depends on the comparison of X and Y:

• If X ≤ Y, the first player wins unless all piles have residue 0 (in which case the second player wins).
• If X > Y, the first player wins only if all piles have residues in [X, X+Y-1]. If any pile has a residue in [0, X-1], the second player wins.

Code Implementation

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

int main() {
    int n, X, Y;
    cin >> n >> X >> Y;
    vector<int> piles(n);
    bool allZero = true;
    for (int i = 0; i < n; i++) {
        cin >> piles[i];
        piles[i] %= (X + Y);
        if (piles[i] != 0) allZero = false;
    }
    if (allZero) {
        cout << "Second" << endl;
        return 0;
    }
    if (X <= Y) {
        cout << "First" << endl;
    } else {
        bool hasSmallResidue = false;
        for (int i = 0; i < n; i++) {
            if (piles[i] < X) {
                hasSmallResidue = true;
                break;
            }
        }
        if (hasSmallResidue) {
            cout << "Second" << endl;
        } else {
            cout << "First" << endl;
        }
    }
    return 0;
}