Editorial for ptit035: Đập đá

Hiểu bài toán

Trò chơi gồm 2 người chơi Ralph (đập đá) và Felix (dán đá) diễn ra luân phiên, Ralph đi trước. Có n cục đá với độ bền ban đầu D_i. Mỗi lượt:

• Ralph chọn một cục đá đang có độ bền > 0 và giảm độ bền đi X. Nếu D_i < X thì độ bền变为 0.
• Felix chọn một cục đá đang có độ bền > 0 và tăng độ bền lên D_i + Y. Felix không thể dán cục đá đã có độ bền 0. Trò chơi diễn ra rất nhiều lượt (999999999). Nếu một người không thể thực hiện hành động (ví dụ Ralph không còn đá để đập, Felix không còn đá để dán), họ có thể bỏ lượt. Mục tiêu: Ralph muốn tối đa hóa số lượng đá có độ bền 0 (bị đập vỡ hoàn toàn) cuối cùng. Felix muốn ngăn cản điều đó. Cả hai chơi tối ưu. Tìm số lượng đá Ralph có thể đập được (độ bền về 0).

Các cách tiếp cận

Cách Phân tích Logic Đơn giản

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

using namespace std;

int main() {
    int n, x, y;
    cin >> n >> x >> y;
    vector<int> D(n);
    int cnt_small = 0;
    for (int i = 0; i < n; i++) {
        cin >> D[i];
        if (D[i] <= x) {
            cnt_small++;
        }
    }

    // Trường hợp 1: X > Y
    // Ralph đánh nhanh hơn Felix sửa. Ralph có thể đập tan mọi viên đá.
    if (x > y) {
        cout << n << endl;
        return 0;
    }

    // Trường hợp 2: X <= Y
    // Felix có thể sửa các viên đá lớn hơn X để giữ chúng tồn tại.
    // Ralph chỉ có thể đập được các viên đá ban đầu có độ bền <= X.
    // Trong số các viên đá này, ai đi trước sẽ chiếm ưu thế.
    // Felix sẽ cố gắng sửa các viên này, Ralph cố gắng đập chúng.
    // Kết quả là số lượng viên đá <= X được chia đôi làm tròn lên.
    cout << (cnt_small + 1) / 2 << endl;

    return 0;
}

• Time Complexity: O(n)
• Space Complexity: O(n)

Đây là cách tiếp cận dựa trên quan sát trực tiếp về tính chất của trò chơi:

1. Nếu X > Y: Ralph giảm độ bền nhanh hơn Felix tăng độ bền. Do số lượt chơi là vô hạn, Ralph có thể chọn một viên đá và đập nó liên tục cho đến khi nó vỡ, ngay cả khi Felix cố gắng sửa. Do đó, Ralph đập được tất cả n viên đá.
2. Nếu X <= Y:
   • Nếu một viên đá có độ bền D > X: Khi Ralph đập, độ bền giảm X, nhưng Felix ngay lập tức có thể tăng Y (với Y >= X) để khôi phục hoặc thậm chí tăng độ bền lên cao hơn. Felix có thể ngăn Ralph đập vỡ các viên đá này. Ralph nên bỏ qua các viên này.
   • Nếu một viên đá có độ bền D <= X: Ralph có thể đập vỡ nó ngay lập tức trong một lượt (giảm D về 0). Tuy nhiên, Felix cũng nhận ra điều này. Nếu Felix được đi trước một viên đá loại này, anh ta sẽ dán nó ngay (tăng D lên D+Y > X), đưa nó vào nhóm viên đá 'không thể đập'.
   • Do đó, trò chơi giữa các viên 'dễ đập' (D <= X) trở thành một cuộc chiến tranh giành quyền kiểm soát: Ralph muốn đập, Felix muốn bảo vệ.
   • Vì Ralph đi trước, anh ta sẽ đập viên đầu tiên. Felix sẽ dán viên tiếp theo. Cứ thế luân phiên.
   • Nếu số lượng viên đá loại này là K, Ralph sẽ đập được số viên là số nguyên của K/2 nếu K chẵn, và (K+1)/2 nếu K lẻ (vì Ralph đi trước).
   • Công thức toán học chung là ceil(K / 2) = (K + 1) / 2 (số nguyên học).

Cách Mô phỏng Trò chơi (Không cần thiết)

// Pseudocode cho mô phỏng (không khuyến khích do phức tạp)
// Giả sử ta mô phỏng từng lượt cho đến khi ổn định
// Tuy nhiên, với số lượt 999999999, mô phỏng trực tiếp là bất khả thi.
// Nhưng logic dẫn đến kết quả là (số viên <= X + 1) / 2.
// Code dưới đây chỉ mang tính chất minh họa logic vòng đời của một viên đá.

void simulate_stone(int D, int X, int Y) {
    // Viên đá D <= X:
    // Turn 1 (Ralph): D = 0 (Ralph thắng).
    // Turn 2 (Felix): Felix không thể dán (vì D=0).
    // Viên đá này bị đập.

    // Viên đá D > X:
    // Turn 1 (Ralph): D = D - X (vẫn > 0).
    // Turn 2 (Felix): D = D - X + Y. Vì Y >= X, D >= D > X.
    // Vòng lặp này tiếp diễn vô hạn, viên đá không bao giờ vỡ.
}

• Time Complexity: O(1) mỗi viên (nhận định logic)
• Space Complexity: O(1)

Cách tiếp cận này không thực sự là mô phỏng mà là phân tích vòng đời của từng viên đá:

• Viên đá có độ bền ban đầu <= X sẽ bị đập vỡ ngay khi Ralph chọn nó, vì Felix không thể can thiệp trước đó (Ralph đi trước) và không thể hồi sinh nó sau đó (vì độ bền về 0).
• Viên đá có độ bền ban đầu > X sẽ không bao giờ bị đập vỡ. Tuy nhiên, Felix không phải là người bị động. Anh ta có thể chọn dán các viên đá <= X ngay khi có cơ hội để ngăn chúng bị đập. Vì Felix là người chơi tối ưu, anh ta sẽ làm điều này. Do đó, vấn đề trở thành một bài toán về thứ tự ưu tiên. Nếu có K viên đá <= X, Ralph muốn đập chúng, Felix muốn giữ chúng. Ralph đập viên 1 -> Bị đập. Felix dán viên 2 -> An toàn. Ralph đập viên 3 -> Bị đập. ... Kết quả là Ralph đập được khoảng một nửa số viên đá này. Điểm mấu chốt là tại sao Felix không thể bảo vệ tất cả? Vì mỗi lần Felix dán một viên, Ralph lại có cơ hội đập viên khác. Felix chỉ có thể dán 1 viên mỗi lượt, Ralph đập 1 viên mỗi lượt. Tỷ lệ 1-1. Vì Ralph đi trước, anh ta đập viên đầu tiên. Felix chỉ còn lại K-1 viên để bảo vệ. Felix sẽ bảo vệ thành công số viên đá còn lại nếu anh ta đi trước số viên đó. Nhưng với K-1 viên, Felix không thể đi trước tất cả (vì Ralph đi trước cả bàn cờ). Điều này dẫn đến xác suất/RNG là (K+1)/2.

Phân tích độ phức tạp

Bài học kinh nghiệm

• Phân loại đá dựa trên giá trị so sánh với X: D <= X (dễ đập) và D > X (khó đập).
• Nếu X > Y, Ralph thắng mọi viên đá.
• Nếu X <= Y, cuộc chiến chỉ xảy ra ở các viên D <= X. Felix không thể bảo vệ các viên D > X (vì Ralph đập không kịp Felix sửa), và Ralph không thể đập các viên D > X (vì Felix sửa được).
• Số viên đá Ralph đập được bằng số nguyên của (số viên D <= X + 1) / 2.

Lỗi thường gặp

• Xử lý sai điều kiện X <= Y: Cố gắng đập các viên D > X là lãng phí lượt chơi (Felix sẽ sửa lại ngay).
• Tính toán sai số lượng đá đập được: Cần công thức (t + 1) / 2 thay vì t / 2 để tính ceil vì Ralph đi trước.
• Bỏ qua trường hợp X > Y: Nhiều người chỉ tập trung vào phân tích X <= Y.
• Độ bền D_i có thể bằng 0 ngay từ đầu: Code cần xử lý chính xác (ví dụ D[i] <= x hay D[i] < x).