Chino’s Take-Away Game

The game ends when only one stone remains. If the initial pile contains an odd count, the first player can always remove exactly one stone, leaving an even number. Any subsequent move by the second player must remove an odd amount (co-prime with the even remainder), again leaving an odd count. By induction the first player eventually takes the last stone. With an even starting pile the second player mirrors the same strategy. Hence the answer is Yes for odd n, otherwise No.

#include <bits/stdc++.h>
using int64 = long long;
int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    int64 n; std::cin >> n;
    std::cout << (n & 1 ? "Yes" : "No") << '\n';
    return 0;
}

Chino’s Notepad (Easy)

All words share prefixes. Build a trie; each edge represents one keystroke, and each backspace costs another. The total moves are 2 × (nodes − 1). The longest word never needs backtracking after its last character, so subtract its length.

#include <bits/stdc++.h>
using int64 = long long;
struct Trie {
    int idx = 0;
    std::vector<std::array<int,26>> nxt{{}};
    int extend() {
        nxt.emplace_back();
        nxt.back().fill(0);
        return idx++;
    }
    int insert(const std::string& s) {
        int cur = 0;
        for (char c : s) {
            int ch = c - 'a';
            if (!nxt[cur][ch]) nxt[cur][ch] = extend();
            cur = nxt[cur][ch];
        }
        return cur;
    }
};
int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    int n, m; std::cin >> n >> m;
    Trie tr;
    int mx = 0;
    for (int i = 0; i < n; ++i) {
        std::string s; std::cin >> s;
        tr.insert(s);
        mx = std::max(mx, (int)s.size());
    }
    while (m--) { int l, r; std::cin >> l >> r; }
    std::cout << (tr.idx - 1) * 2 - mx << '\n';
    return 0;
}

Chino’s Marbles

Two fleets of equal-mass balls move on the real line—right-going set R and left-going set L. Collisions are elastic swaps. The k-th collision occurs at the k-th smallest meeting time among pairs (x∈R, y∈L) with x<y. Binary-search the minimal t such that atleast k pairs satisfy y ≤ x+2t.

#include <bits/stdc++.h>
using int64 = long long;
int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    int n, k; std::cin >> n >> k;
    std::vector<int> L, R;
    for (int i = 0, x, dir; i < n; ++i) {
        std::cin >> x >> dir;
        (dir == 1 ? R : L).push_back(x);
    }
    std::ranges::sort(R); std::ranges::sort(L);
    int64 possible = 0;
    for (int x : R)
        possible += L.end() - std::upper_bound(L.begin(), L.end(), x);
    if (R.empty() || L.empty() || R.front() > L.back() || possible < k) {
        std::cout << "No\n";
        return 0;
    }
    std::cout << "Yes\n";
    constexpr double eps = 1e-7;
    auto enough = [&](double t) {
        int64 cnt = 0;
        for (int x : R) {
            auto lo = std::upper_bound(L.begin(), L.end(), x);
            auto hi = std::upper_bound(L.begin(), L.end(), x + 2 * t);
            cnt += hi - lo;
        }
        return cnt >= k;
    };
    double lo = 0, hi = L.back() - R.front();
    while (hi - lo > eps) {
        double mid = (lo + hi) / 2;
        (enough(mid) ? hi : lo) = mid;
    }
    std::cout << std::fixed << std::setprecision(6) << lo << '\n';
    return 0;
}

Chino’s Hide-and-Seek

Solve the system x1+x2+x3=A, x3+x4+x5=B, x5+x6+x1=C. Adding the equations gives 2(x1+x3+x5)+(x2+x4+x6)=A+B+C. Let X=x1+x3+x5 and Y=x2+x4+x6. Then X+Y=N and 2X+Y=A+B+C. Solving yields X=A+B+C−N, Y=2N−(A+B+C). Non-negative solutions exist iff N ≤ A+B+C ≤ 2N.

#include <bits/stdc++.h>
int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    int t; std::cin >> t;
    while (t--) {
        int n, a, b, c; std::cin >> n >> a >> b >> c;
        std::cout << (a + b + c >= n && a + b + c <= 2 * n ? "Yes\n" : "No\n");
    }
    return 0;
}

Chino and Remainders

To sum the k largest remainders of N mod i (1≤i≤N), binary-search the threshold value v such that exactly k remainders are ≥ v. For each divisor segment [l,r] with q=N/l, remainders decrease arithmetically. Count and sum the qualifying remainders in O(√N log N).

#include <bits/stdc++.h>
using int64 = long long;
int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    int N, K; std::cin >> N >> K;
    int val = 0, cntBelow = 0;
    int lo = 1, hi = N;
    while (lo <= hi) {
        int mid = (lo + hi) / 2;
        int total = 0;
        for (int l = 1, r; l <= N; l = r + 1) {
            r = N / (N / l);
            int rem = N % l;
            int q = N / l;
            if (rem < mid) continue;
            int take = std::min((rem - mid) / q + 1, r - l + 1);
            total += take;
        }
        if (total >= K) lo = mid + 1;
        else {
            cntBelow = total;
            val = mid;
            hi = mid - 1;
        }
    }
    int64 ans = int64(K - cntBelow) * (val - 1);
    for (int l = 1, r; l <= N; l = r + 1) {
        r = N / (N / l);
        int rem = N % l;
        int q = N / l;
        if (rem < val) continue;
        int len = std::min((rem - val) / q + 1, r - l + 1);
        ans += int64(rem * 2 - q * (len - 1)) * len / 2;
    }
    std::cout << ans << '\n';
    return 0;
}

Chino’s Inversions

Concatenate the given strictly increasing runs into one sequence a while remembering the original run index of every element. Compute the initial inversion count. If it already exceeds k, output No. Otherwise repeatedly swap adjacent elements belonging to different runs whenever the left element is smaller than the right, each swap increasing the inversion count by one, until the desired k is reached or proven impossible.

#include <bits/stdc++.h>
int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    int n, k; std::cin >> n >> k;
    std::vector<std::vector<int>> seqs(n);
    for (int i = 0; i < n; ++i) {
        int len; std::cin >> len;
        seqs[i].resize(len);
        for (int& v : seqs[i]) std::cin >> v;
    }
    std::ranges::sort(seqs, [](auto& a, auto& b) { return a[0] < b[0]; });
    std::vector<std::pair<int,int>> flat;
    for (int id = 0; id < n; ++id)
        for (int v : seqs[id]) flat.emplace_back(id, v);
    auto inv = [&] {
        int res = 0;
        for (int i = 0; i < flat.size(); ++i)
            for (int j = i + 1; j < flat.size(); ++j)
                if (flat[i] > flat[j]) ++res;
        return res;
    };
    k -= inv();
    if (k < 0) { std::cout << "No\n"; return 0; }
    for (int i = 0; i < flat.size(); ++i)
        for (int j = 0; j + 1 < flat.size(); ++j)
            if (flat[j].first != flat[j+1].first && flat[j].second < flat[j+1].second && k) {
                std::swap(flat[j], flat[j+1]);
                --k;
            }
    if (k) { std::cout << "No\n"; return 0; }
    std::cout << "Yes\n";
    for (int i = 0; i < flat.size(); ++i)
        std::cout << flat[i].second << " \n"[i + 1 == flat.size()];
    return 0;
}

Chino’s Triangle Walk

Label the vertices of the triangular grid row by row from top to bottom, left to right. A Hamiltonian path is obtained by zig-zagging right-down-left across rows, then returning along the left edge.

#include <bits/stdc++.h>
int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    int n; std::cin >> n; ++n;
    std::cout << "Yes\n";
    std::vector<std::vector<int>> id(n+1, std::vector<int>(n+1));
    int cnt = 0;
    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= i; ++j) id[i][j] = ++cnt;
    for (int i = 2; i <= n; ++i) {
        std::cout << id[i-1][i-1] << ' ';
        for (int j = i; j < n; ++j) std::cout << id[j][i] << ' ' << id[j][i-1] << ' ';
        for (int j = n; j > i; --j) std::cout << id[j][i] << ' ';
    }
    int x = n*(n+1)/2;
    for (int j = 0; j < n; --x, ++j) std::cout << x << ' ';
    for (int i = n-1; i; --i) {
        x -= i;
        std::cout << x+1 << ' ';
    }
    return 0;
}

Chino’s Ox Puzzle

Sort the input string and compare with "cdenoorw". A match prints happy new year, otherwise I AK IOI.

#include <bits/stdc++.h>
int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    std::string s; std::cin >> s;
    std::string target = "cdenoorw";
    std::ranges::sort(s);
    std::cout << (s == target ? "happy new year\n" : "I AK IOI\n");
    return 0;
}