Mức độ khó: Đỏ, Cam, Vàng, Xanh lá, Xanh dương, Tím, Đen, Đen

Bài A

Cho hai số nguyên a và b, giải bất phương trình b - 2x ≤ a - x với điều kiện 0 ≤ x ≤ a. Yêu cầu in ra giá trị nhỏ nhất của a - x.

Sau khi biến đổi, ta có x ≥ b - a. Từ đó, ta xét các trường hợp để tìm nghiệm tối ưu.

#include <cstdio>
using namespace std;

int main() {
    int t, a, b;
    scanf("%d", &t);
    while (t--) {
        scanf("%d%d", &a, &b);
        if (a >= b) {
            printf("%d\n", a);
        } else {
            int min_x = b - a;
            if (min_x <= a) {
                printf("%d\n", a - min_x);
            } else {
                printf("0\n");
            }
        }
    }
    return 0;
}

Bài B

Có một máy bán nước chanh tự động với n ngăn và n nút bấm. Mỗi lần nhấn nút, nếu ngăn tương ứng còn nước thì một chai sẽ rơi xuống. Bạn không biết nút nào tương ứng ngăn nào, nhưng biết trước số lượng chai trong từng ngăn. Tìm số lần nhấn ít nhất để lấy được ít nhất k chai.

Chiến lược: Dùng đống cực tiểu để lần lượt xử lý các ngăn có ít chai nhất trước, giảm dần số nút cần thử theo từng vòng.

#include <queue>
#include <vector>
#include <cstdio>
using namespace std;

typedef long long ll;

int main() {
    ll t, n, k;
    scanf("%lld", &t);
    while (t--) {
        priority_queue<ll, vector<ll>, greater<ll>> pq;
        scanf("%lld%lld", &n, &k);
        for (ll i = 0; i < n; ++i) {
            ll x;
            scanf("%lld", &x);
            pq.push(x);
        }

        ll remaining_slots = n;
        ll base_presses = 0;
        ll total_presses = 0;

        while (true) {
            ll current_min = pq.top();
            ll diff = current_min - base_presses;

            if (diff * remaining_slots >= k) {
                total_presses += k;
                break;
            }

            total_presses += diff * remaining_slots + 1;
            k -= diff * remaining_slots;
            base_presses = current_min;
            pq.pop();
            --remaining_slots;
        }

        printf("%lld\n", total_presses);
    }
    return 0;
}

Bài C

Cho n cặp số, hãy sắp xếp lại sao cho số cặp nghịch thế trong dãy ghép là nhỏ nhất.

Nhận xét: Sắp xếp theo tổng hai phần tử trong mỗi cặp theo thứ tự tăng dần sẽ cho kết quả tối ưu.

#include <algorithm>
#include <cstdio>
using namespace std;

struct Pair {
    int first, second;
};

bool compare(Pair x, Pair y) {
    return x.first + x.second < y.first + y.second;
}

int main() {
    int t, n;
    scanf("%d", &t);
    while (t--) {
        scanf("%d", &n);
        Pair arr[100010];
        for (int i = 0; i < n; ++i) {
            scanf("%d%d", &arr[i].first, &arr[i].second);
        }
        sort(arr, arr + n, compare);
        for (int i = 0; i < n; ++i) {
            printf("%d %d ", arr[i].first, arr[i].second);
        }
        printf("\n");
    }
    return 0;
}

Bài D

Prokhor tham gia cuộc thi gồm n bài. Khi làm bài i, anh có thể chọn giải (nhận điểm a_i) hoặc bỏ qua (chuyển tới bài b_i). Sau khi giải xong bài i, anh chỉ có thể quay lại bài có chỉ số nhỏ hơn hoặc bằng i. Tìm cách làm để đạt điểm cao nhất.

Chuyển bài toán thành đồ thị: mỗi đỉnh nối tới i-1 với trọng số 0 (nếu giải), hoặc tới b_i với trọng số a_i (nếu bỏ). Dùng Dijkstra để tìm đường đi ngắn nhất từ đỉnh 1 tới mọi đỉnh, rồi tính điểm tối đa = tổng điểm prefix - chi phí đường đi.

#include <queue>
#include <vector>
#include <cstring>
#include <cstdio>
using namespace std;

typedef long long ll;
const ll INF = 1e18;

struct Edge {
    int to;
    ll weight;
};

struct State {
    int node;
    ll dist;
    bool operator>(const State& other) const {
        return dist > other.dist;
    }
};

vector<Edge> graph[400005];
ll dist[400005];
bool visited[400005];

void dijkstra(int start, int n) {
    fill(dist, dist + n + 1, INF);
    fill(visited, visited + n + 1, false);
    priority_queue<State, vector<State>, greater<State>> pq;
    dist[start] = 0;
    pq.push({start, 0});

    while (!pq.empty()) {
        State cur = pq.top(); pq.pop();
        if (visited[cur.node]) continue;
        visited[cur.node] = true;

        for (auto& edge : graph[cur.node]) {
            if (!visited[edge.to] && dist[cur.node] + edge.weight < dist[edge.to]) {
                dist[edge.to] = dist[cur.node] + edge.weight;
                pq.push({edge.to, dist[edge.to]});
            }
        }
    }
}

int read_int() {
    int x = 0; char c = getchar();
    while (c < '0' || c > '9') c = getchar();
    while (c >= '0' && c <= '9') { x = x * 10 + c - '0'; c = getchar(); }
    return x;
}

void write_int(ll x) {
    if (x > 9) write_int(x / 10);
    putchar(x % 10 + '0');
}

int main() {
    int t = read_int();
    while (t--) {
        int n = read_int();
        for (int i = 1; i <= n; ++i) graph[i].clear();

        ll prefix[400005] = {0};
        for (int i = 1; i <= n; ++i) {
            ll score = read_int();
            prefix[i] = prefix[i - 1] + score;
            if (i > 1) graph[i].push_back({i - 1, 0});
        }

        for (int i = 1; i <= n; ++i) {
            int jump_to = read_int();
            graph[i].push_back({jump_to, prefix[i] - prefix[i - 1]});
        }

        dijkstra(1, n);

        ll max_score = 0;
        for (int i = 1; i <= n; ++i) {
            max_score = max(max_score, prefix[i] - dist[i]);
        }

        write_int(max_score);
        putchar('\n');
    }
    return 0;
}

Bài E

Cho hai đồ thị mạnh liên thông, thêm n cạnh có hướng giữa chúng sao cho mọi chu trình đều có độ dài chia hết cho k, mỗi đỉnh "vào" có đúng một cạnh vào, mỗi đỉnh "ra" có đúng một cạnh ra, và mọi cạnh nối từ đồ thị này sang đồ thị kia.

Ý tưởng: Gán màu modulo k cho các đỉnh sao cho mỗi cạnh đi từ màu c sang (c+1) mod k. Kiểm tra tính khả thi bằng cách so sánh mảng đếm màu giữa hai đồ thị — nếu một mảng là dịch vòng của mảng kia thì thỏa mãn. Dùng thuật toán KMP để kiểm tra dịch vòng.