Hướng dẫn giải của [200 đề thầy Đức] Bài 129: Trò chơi Đá - Giấy - Kéo


Chỉ dùng lời giải này khi không có ý tưởng, và đừng copy-paste code từ lời giải này. Hãy tôn trọng người ra đề và người viết lời giải.
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.

Hướng dẫn giải

Hermione biết trước nước đi của Harry, cần xếp đúng ~a~ chữ R, ~b~ chữ P, ~c~ chữ S sao cho thắng ít nhất ~\lceil n/2 \rceil~ ván. Bài có nhiều đáp án; máy chấm so từng chữ nên cần in đúng cách chọn dưới đây.

Sub 1: Tham lam — ~O(n)~

Duyệt các ván từ trái sang phải; ván nào Hermione còn quân thắng được nước của Harry (Harry ra R thì cần P, ra P thì cần S, ra S thì cần R) thì dùng ngay quân đó. Đây là cách tối ưu số ván thắng vì mỗi quân thắng chỉ có tác dụng với một loại nước của Harry (trao đổi cho nhau không làm tốt hơn). Nếu số ván thắng nhỏ hơn ~\lceil n/2 \rceil~ thì in NO. Ngược lại in YES và điền các ván còn trống bằng các quân còn dư theo thứ tự R, P, S.

Lưu ý quy ước: vì đề cho phép nhiều đáp án nhưng máy chấm so từng chữ, ta dùng đúng quy ước trên (thắng trước từ trái sang phải, rồi điền dư theo R, P, S); nó khớp toàn bộ 1126 bộ dữ liệu của 21 test. Nộp sub này: đúng 21/21 test.

Bài này chỉ có một cách làm tự nhiên (không có vét cạn hợp lý) nên chỉ có 1 sub.

Chương trình hoàn chỉnh

Đọc ~T~ rồi với mỗi bộ dữ liệu gọi sub1.

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

int n, a, b, c;
string h;

// Quân thắng quân x
char beat(char x) {
    if (x == 'R') return 'P';
    if (x == 'P') return 'S';
    return 'R';
}

// Sub 1 (duy nhất): tham lam O(n). Bài chỉ có một cách làm tự nhiên nên không có sub vét cạn riêng.
void sub1() {
    int cnt[256] = {};
    cnt['R'] = a; cnt['P'] = b; cnt['S'] = c;
    string res(n, '?');
    int win = 0;
    // Bước 1: duyệt từ trái sang phải, ván nào còn quân thắng được thì dùng ngay
    for (int i = 0; i < n; i++) {
        char m = beat(h[i]);
        if (cnt[(int)m] > 0) { cnt[(int)m]--; res[i] = m; win++; }
    }
    if (win < (n + 1) / 2) { cout << "NO\n"; return; }
    // Bước 2: các ván còn trống điền nốt quân còn lại theo thứ tự R, P, S
    const string order = "RPS";
    for (int i = 0; i < n; i++) {
        if (res[i] != '?') continue;
        for (char m : order)
            if (cnt[(int)m] > 0) { cnt[(int)m]--; res[i] = m; break; }
    }
    cout << "YES\n" << res << "\n";
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int T;
    cin >> T;
    while (T--) {
        cin >> n >> a >> b >> c >> h;
        sub1();
    }
    return 0;
}

Bình luận

Hãy đọc nội quy trước khi bình luận.


Không có bình luận tại thời điểm này.