A. Chuỗi Năm Mới Đầu tiên, duyệt qua toàn bộ chuỗi để đếm số lần xuất hiện của "2025" và "2026". Nếu số lần xuất hiện của "2025" là 0 hoặc số lần xuất hiện của "2026" không phải là 0, thì không cần thay đổi gì. Ngược lại, nếu có ít nhất một "2025", ta sẽ thay đổi chữ số '5' cuối cùng thành '6'. Như vậy, số lần xuất hiện của "2026" sẽ không còn là 0, và chỉ cần thay đổi một lần.

Xem mã nguồn

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

int n;
string s;

void solve() {
    cin >> n >> s;
    int count_2025 = 0, count_2026 = 0;

    for (int i = 0; i + 3 < n; ++i) {
        if (s[i] == '2' && s[i+1] == '0' && s[i+2] == '2') {
            if (s[i+3] == '5') count_2025++;
            else if (s[i+3] == '6') count_2026++;
        }
    }

    if (count_2026 || !count_2025) cout << 0 << '\n';
    else cout << 1 << '\n';
}

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

B. Bánh Mới Năm Có hai cách phân chia: chocolate trắng cho các tầng lẻ, chocolate đen cho các tầng chẵn; hoặc ngược lại. Cách tính số tầng tối đa cho cả hai cách phân chia này là giống nhau. Đầu tiên, tính toán lượng chocolate cần thiết cho mỗi tầng, sau đó tạo hai tổng tiền tố, một tổng chỉ bao gồm các tầng lẻ, và một tổng chỉ bao gồm các tầng chẵn. Tính toán số tầng cuối cùng mà tổng lượng chocolate cung cấp đủ cho các tầng đó, và lấy giá trị nhỏ nhất giữa hai cách phân chia.

Xem mã nguồn

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

int x, y;
vector<int> v, q1, q2;

void solve() {
    cin >> x >> y;
    int ans;

    int a = upper_bound(q1.begin(), q1.end(), x) - q1.begin() - 1;
    int b = upper_bound(q2.begin(), q2.end(), y) - q2.begin() - 1;
    a++; b++;
    ans = min(a, b);

    swap(x, y);

    a = upper_bound(q1.begin(), q1.end(), x) - q1.begin() - 1;
    b = upper_bound(q2.begin(), q2.end(), y) - q2.begin() - 1;
    a++; b++;
    ans = max(ans, min(a, b));

    cout << ans << '\n';
}

int main() {
    int _ = 1;
    while (_ <= 1e6)
        v.push_back(_), _ *= 2;
    _ = 0;
    for (int i = 0; i < v.size(); ++i) {
        if (i % 2 == 0) _ += v[i];
        q1.push_back(_);
    }
    _ = 0;
    q2.push_back(0);
    for (int i = 1; i < v.size(); ++i) {
        if (i % 2 == 1) _ += v[i];
        q2.push_back(_);
    }
    cin >> _;
    while (_--) solve();
    return 0;
}

C. Sản Xuất Người Tuyết Tính số bộ ba ((i, j, k)) không thỏa mãn điều kiện, sau đó trừ đi từ tổng số bộ ba. Điều kiện không thỏa mãn là tồn tại (o) sao cho (a_{i+o} \geq b_{j+o}) hoặc (b_{j+o} \geq c_{k+o}). Tính số bộ ba chỉ thỏa mãn (a_{i+o} \geq b_{j+o}) bằng cách duyệt (i) và (j), nếu (a_i \geq b_j) thì cộng (n \times n) vào số bộ ba không hợp lệ. Tiếp theo, tính số bộ ba chỉ thỏa mãn (b_{j+o} \geq c_{k+o}) tương tự, nhưng phải trừ đi số bộ ba đã tính ở bước trước.

Xem mã nguồn

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

#define int long long

int n;
int a[5005], b[5005], c[5005];

void solve() {
    cin >> n;
    for (int i = 0; i < n; ++i) cin >> a[i];
    for (int i = 0; i < n; ++i) cin >> b[i];
    for (int i = 0; i < n; ++i) cin >> c[i];

    int ans = n * n * n, le = 0;

    for (int o = 0; o < n; ++o) {
        bool fl = 0;
        for (int i = 0; i < n; ++i)
            if (a[i] >= b[(i + o) % n]) {
                fl = 1;
                break;
            }
        if (fl) ans -= n * n, le += n;
    }

    for (int o = 0; o < n; ++o) {
        bool fl = 0;
        for (int i = 0; i < n; ++i)
            if (b[i] >= c[(i + o) % n]) {
                fl = 1;
                break;
            }
        if (fl) ans -= n * n - le;
    }

    cout << ans << '\n';
}

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

D. Trang Trí Cây Giáng Sinh Đặt lại bài toán: sắp xếp lại mảng (a_1) đến (a_n) và sử dụng một con trỏ (p) di chuyển từ 1 đến (n), mỗi lần giảm (a_p) đi 1. Nếu (a_p) không thể giảm, giảm (a_0). Nếu cả (a_p) và (a_0) đều không thể giảm, sắp xếp không hợp lệ. Tính số cách sắp xếp hợp lệ.

Xem mã nguồn

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

#define int long long
#define mod 998244353

int n;
int a[55];

int power(int a, int b) {
    if (b == 0) return 1;
    int z = power(a, b / 2);
    z *= z; z %= mod;
    if (b % 2) z *= a;
    return z % mod;
}

int factorial[55];
int inverse_factorial[55];

int combination(int n, int m) {
    return factorial[n] * inverse_factorial[m] % mod * inverse_factorial[n - m] % mod;
}

void solve() {
    cin >> n;
    int sum = 0;
    for (int i = 0; i <= n; ++i) cin >> a[i], sum += a[i];
    int gs = sum / n;

    for (int i = 1; i <= n; ++i) {
        if (a[i] >= gs) a[i] -= gs;
        else a[0] -= gs - a[i], a[i] = 0;
    }

    if (a[0] < 0) {
        cout << 0 << '\n';
        return;
    }

    int cnt0, cnt1; cnt0 = cnt1 = 0;
    for (int i = 1; i <= n; ++i) {
        if (a[i] != 0 && a[i] != 1) {
            cout << 0 << '\n';
            return;
        }
        if (a[i]) cnt1++;
        else cnt0++;
    }

    int al = cnt1 + a[0];

    int ans = combination(al, cnt1) % mod;
    ans *= factorial[cnt1]; ans %= mod;
    ans *= factorial[cnt0]; ans %= mod;

    cout << ans << '\n';
}

int main() {
    factorial[0] = 1;
    for (int i = 1; i <= 52; ++i)
        factorial[i] = factorial[i - 1] * i % mod;
    inverse_factorial[52] = power(factorial[52], mod - 2);
    for (int i = 51; i >= 0; --i)
        inverse_factorial[i] = inverse_factorial[i + 1] * (i + 1) % mod;

    int t; cin >> t;
    while (t--) solve();
    return 0;
}

E. Quà Tặng Năm Mới Xem mã nguồn

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

#define int long long

int n, m, k;
int a[200005];
struct Node {
    int x, y, z, gs;
} c[200005];

bool compare(Node o, Node t) {
    if (o.gs == t.gs) return o.z - o.y < t.z - t.y;
    return o.gs < t.gs;
}

priority_queue<int> pq;
priority_queue<int, vector<int>, greater<int>> pq2;

void solve() {
    cin >> n >> m >> k;

    for (int i = 1; i <= m; ++i) cin >> a[i];
    sort(a + 1, a + 1 + m);
    for (int i = 1; i <= n; ++i) {
        cin >> c[i].x >> c[i].y >> c[i].z;
        c[i].gs = lower_bound(a + 1, a + 1 + m, c[i].x) - a;
        k -= c[i].y;
    }

    sort(c + 1, c + 1 + n, compare);

    pq.push(c[1].z - c[1].y);
    int wl = c[1].gs;
    c[n + 1].gs = m + 1;
    for (int i = 2; i <= n + 1; ++i) {
        if (c[i].gs != c[i - 1].gs) {
            int wr = c[i].gs - 1;
            while (!pq.empty() && wl <= wr) pq.pop(), wl++;
            wl = wr + 1;
        }
        if (i != n + 1) pq.push(c[i].z - c[i].y);
    }

    int ans = n - pq.size();

    while (!pq.empty()) pq2.push(pq.top()), pq.pop();

    while (!pq2.empty() && pq2.top() <= k) {
        k -= pq2.top(); pq2.pop();
        ans++;
    }

    cout << ans << '\n';

    while (!pq2.empty()) pq2.pop();
}

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