hpr25

Truyền Số

Time limit: 1.0 / Memory limit: 256M

Point: 100

Đây là bài giới thiệu cơ bản về dạng 2-Steps (Communication).

Hãy tưởng tượng có hai người A và B. Bạn là ban giám khảo, có một số nguyên dương ~n~, và bạn sẽ gửi số này cho người A. Người A và B cần hợp tác làm sao để B biết được số đó.

Khi nhận được số ~n~ từ bạn, người A chỉ có thể gửi thông tin cho người B bằng một xâu nhị phân với độ dài <= 40.

Khi nhận được xâu nhị phân, người B sẽ phải từ đó suy ra số ~n~ ban đầu và trả về số đó.

Các thao tác sẽ được thực hiện như trong đoạn code dưới đây:

#include <iostream>
#include <string>

using namespace std;

namespace A {
    string encode(int n) {
        // your code goes here;
    }
}

namespace B {
    int decode(string s) {
        // your code goes here
    }
}

namespace jury {
    const int Length = 40;
    bool check_valid(string &s) {
        for (char &c : s) {
            if (c != '0' && c != '1') return false;
        }

        return s.size() <= Length;
    }

    int solve() {
        int n; cin >> n;
        string val = A::encode(n);
        cout << n << ' ' << val << endl;
        if (!check_valid(val)) {
            return false;
        }
        return B::decode(val) == n;
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout << jury::solve(); // 1 if True, otherwise False
}

Nhiệm vụ của bạn là hoàn thiện hai hàm A::encode (nén mã) và B::decode (giải mã).

Lưu ý rằng hãy nộp thẳng tất cả code. Vì đây chỉ là bài để giới thiệu nên grader được đưa thẳng, đi thi thì chúng ta sẽ biết rằng luồng chạy của Encode và Decode là khác hẳn nhau, sẽ không biết các biến của nhau!

Sample Input

Giả sử bạn cho ~A~ giá trị ~n = 3~.

~A~ encode ~n~ thành string 111

~B~ nhận string 111 và hiểu ý của ~A~, trả về ~3~.

Coins

Nộp bài

Time limit: 1.0 / Memory limit: 256M

Point: 100

Alice, kẻ thù của Bob, đã bắt giữ hai người con gái của Bob là Benny và Bynnen. Hắn đồng ý thả họ nếu họ giải được một câu đố.

Alice có một bàn cờ ~8 \times 8~, các ô được đánh số từ ~0~ đến ~63~ theo thứ tự từ trái sang phải, từ trên xuống dưới:

0  1  2  3  4  5  6  7
8  9  10 11 12 13 14 15
16 17 18 19 20 21 22 23
24 25 26 27 28 29 30 31
32 33 34 35 36 37 38 39
40 41 42 43 44 45 46 47
48 49 50 51 52 53 54 55
56 57 58 59 60 61 62 63

Trên mỗi ô có một đồng xu. Ô có nhãn ~c~ chứa một đồng xu bị nguyền rủa, nhưng về hình thức thì nó hoàn toàn giống các đồng xu còn lại. Mỗi đồng xu đang ở một trong hai trạng thái: ngửa (~0~) hoặc úp (~1~).

Sau bữa tối, hai chị em bị đưa vào hai phòng khác nhau. Alice vào phòng của Benny, đưa cho cô ấy bàn cờ hiện tại và cho biết giá trị ~c~. Benny không được thay đổi vị trí các đồng xu, nhưng có thể lật từ ~1~ đến ~k~ đồng xu. Một đồng xu có thể bị lật nhiều lần.

Sau đó Alice đem bàn cờ sau khi đã lật sang cho Bynnen. Nếu Bynnen xác định đúng ô chứa đồng xu bị nguyền rủa thì cả hai sẽ được thả.

Hai chị em được phép thống nhất chiến lược trước bữa tối, nhưng không được liên lạc sau đó.

Nhiệm vụ

Bạn cần cài đặt hai thủ tục:

namespace A {
    std::vector<int> coin_flips(std::vector<int> b, int c);
}

namespace B {
    int find_coin(std::vector<int> b);
}

A::coin_flips đóng vai Benny.
B::find_coin đóng vai Bynnen.

Ý nghĩa các hàm

`A::coin_flips`

~b~ là mảng độ dài ~64~.
~b[i]~ bằng ~0~ nếu đồng xu ở ô ~i~ đang ngửa, bằng ~1~ nếu đang úp.
~c~ là vị trí của đồng xu bị nguyền rủa.
Hàm phải trả về danh sách các ô mà Benny sẽ lật.
Độ dài danh sách phải nằm trong đoạn ~[1, k]~.
Một chỉ số có thể xuất hiện nhiều lần.

`B::find_coin`

~b~ là trạng thái bàn cờ sau khi Benny đã lật xong.
Hàm phải trả về đúng chỉ số ~c~.

Lưu ý chấm

HNOJ không hỗ trợ chấm bài này dưới dạng hai chương trình riêng biệt, nên file mẫu sol.cpp đã gộp cả hai namespace vào cùng một chương trình.

Vậy nên bạn sẽ được cung cấp một khung code như sau, lưu ý chỉ code vào namespace A và B, không được dùng biến toàn cục.

#include <iostream>
#include <string>
#include <vector>
using namespace std;

namespace jury {
    extern int K;
}

namespace A {
    vector<int> coin_flips(vector<int> b, int c) {
        (void)b;
        (void)c;
        // Hoan thien ham nay.
        // Neu can, ban co the doc gioi han so lan lat qua jury::K.
        return {};
    }
}

namespace B {
    int find_coin(vector<int> b) {
        (void)b;
        // Hoan thien ham nay.
        return 0;
    }
}

namespace jury {
    const int BOARD_SIZE = 64;
    const int SIDE = 8;
    int K;

    struct Verdict {
        bool ok;
        int passed;
        int total;
        int failed_case;
        string reason;
    };

    bool read_board(vector<int> &b) {
        b.assign(BOARD_SIZE, 0);
        for (int row = 0; row < SIDE; row++) {
            string s;
            if (!(cin >> s)) {
                return false;
            }
            if ((int)s.size() != SIDE) {
                return false;
            }
            for (int col = 0; col < SIDE; col++) {
                if (s[col] != '0' && s[col] != '1') {
                    return false;
                }
                b[row * SIDE + col] = s[col] - '0';
            }
        }
        return true;
    }

    bool valid_flips(const vector<int> &flips, string &reason) {
        if ((int)flips.size() < 1 || (int)flips.size() > K) {
            reason = "so luong dong xu bi lat nam ngoai doan [1, K]";
            return false;
        }
        for (int x : flips) {
            if (x < 0 || x >= BOARD_SIZE) {
                reason = "chi so dong xu khong hop le";
                return false;
            }
        }
        return true;
    }

    bool solve_case(vector<int> b, int c, string &reason) {
        if (c < 0 || c >= BOARD_SIZE) {
            reason = "chi so dong xu bi nguyen rua khong hop le";
            return false;
        }

        vector<int> flips = A::coin_flips(b, c);
        if (!valid_flips(flips, reason)) {
            return false;
        }

        for (int x : flips) {
            b[x] ^= 1;
        }

        if (B::find_coin(b) != c) {
            reason = "B::find_coin tra ve sai dap an";
            return false;
        }
        return true;
    }

    Verdict solve() {
        int t;
        if (!(cin >> K >> t)) {
            return {false, 0, 0, 0, "khong doc duoc k va T"};
        }
        if (K < 1 || K > BOARD_SIZE || t < 1 || t > 1000) {
            return {false, 0, t, 0, "k hoac T nam ngoai gioi han"};
        }

        int passed = 0;
        for (int tc = 0; tc < t; tc++) {
            int c;
            vector<int> b;
            if (!(cin >> c) || !read_board(b)) {
                return {false, passed, t, tc + 1, "input scenario khong hop le"};
            }
            string reason;
            if (!solve_case(b, c, reason)) {
                return {false, passed, t, tc + 1, reason};
            }
            passed++;
        }

        return {true, passed, t, 0, ""};
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    jury::Verdict verdict = jury::solve();
    if (verdict.ok) {
        cout << "OK\n";
        cout << verdict.passed << ' ' << verdict.total << '\n';
    } else {
        cout << "WA\n";
        cout << verdict.passed << ' ' << verdict.total << '\n';
        cout << verdict.failed_case << '\n';
        cout << verdict.reason << '\n';
    }
    return 0;
}

Định dạng input của bộ chấm cục bộ

Dòng 1: hai số nguyên ~k~ và ~T~.
Với mỗi scenario:
Dòng 1: số nguyên ~c~.
~8~ dòng tiếp theo: mỗi dòng là một xâu nhị phân độ dài ~8~, mô tả một hàng của bàn cờ.

Định dạng output

Nếu vượt qua toàn bộ scenario, chương trình in:

OK
so_scenario_dung tong_so_scenario

Nếu có lỗi, chương trình in:

WA
so_scenario_dung tong_so_scenario
chi_so_scenario_loi_dau_tien
ly_do

Ràng buộc

~1 \le T \le 1000~
~1 \le k \le 64~
~0 \le c \le 63~

Các scenario là độc lập với nhau. Chiến lược của bạn không được phụ thuộc vào thứ tự xuất hiện của scenario.

Subtasks

(10 điểm) ~c < 2~, ~k = 1~
(15 điểm) ~c < 3~, ~k = 1~
(10 điểm) ~k = 64~
(15 điểm) ~k = 8~
(50 điểm) ~k = 1~

Ví dụ

Input

Output

OK
1 1

Ghi chú

Trong ví dụ trên, chỉ có một scenario, ~k = 1~, và đồng xu bị nguyền rủa ở ô ~63~. Nếu lời giải của bạn chọn đúng một đồng xu để lật sao cho B::find_coin luôn suy ra lại được ~63~, bộ chấm sẽ in OK.

Transfer

Nộp bài

Time limit: 1.0 / Memory limit: 256M

Point: 100

Araz có một dãy nhị phân gồm ~N~ bit và muốn gửi nó cho Baba. Vì dữ liệu có thể bị lỗi trong quá trình truyền, Araz được phép gắn thêm một dãy nhị phân độ dài ~K~ vào cuối dãy gốc để Baba có thể khôi phục lại dãy ban đầu ngay cả khi tối đa một bit trong toàn bộ dữ liệu truyền đi bị đảo.

Nhiệm vụ của bạn là giúp Araz và Baba thực hiện việc gửi và nhận dữ liệu sao cho ~K~ là nhỏ nhất có thể.

Nhiệm vụ

Bạn cần cài đặt hai thủ tục:

namespace A {
    std::vector<int> get_attachment(std::vector<int> source);
}

namespace B {
    std::vector<int> retrieve(std::vector<int> data);
}

A::get_attachment đóng vai Araz.
B::retrieve đóng vai Baba.

Ý nghĩa các hàm

`A::get_attachment`

source là mảng nhị phân độ dài ~N~.
Hàm phải trả về một mảng nhị phân độ dài ~K~, sẽ được nối vào sau source.
Phải luôn có ~K \le 2N~.

`B::retrieve`

data là mảng nhị phân độ dài ~N + K~, có thể đã bị lỗi tối đa một bit.
Hàm phải trả về đúng dãy gốc source, tức một mảng nhị phân độ dài ~N~.

Điều kiện đúng

Xét một hàm manipulate nhận một dãy nhị phân và có thể đảo tối đa một bit bất kỳ trong dãy đó.

Gọi:

~ data = source \; || \; get\_attachment(source) ~

trong đó ~||~ là phép nối dãy.

Lời giải được coi là đúng nếu với mọi source và mọi cách chọn manipulate, ta luôn có:

~~ retrieve(manipulate(data)) = source ~~

Lưu ý chấm

HNOJ không hỗ trợ chấm bài này dưới dạng hai chương trình riêng biệt, nên file mẫu sol.cpp đã gộp cả hai namespace vào cùng một chương trình.

Vậy nên bạn sẽ được cung cấp một khung code như sau, lưu ý chỉ code vào namespace A và B, không được dùng biến toàn cục.

#include <algorithm>
#include <iostream>
#include <string>
#include <vector>
using namespace std;

namespace A {
    vector<int> get_attachment(vector<int> source) {
        (void)source;
        // Hoan thien ham nay.
        return {};
    }
}

namespace B {
    vector<int> retrieve(vector<int> data) {
        (void)data;
        // Hoan thien ham nay.
        return {};
    }
}

namespace jury {
    struct Verdict {
        bool ok;
        int passed;
        int total;
        int max_k;
        int failed_case;
        string reason;
    };

    bool read_source(int n, vector<int> &source) {
        string s;
        if (!(cin >> s) || (int)s.size() != n) {
            return false;
        }
        source.assign(n, 0);
        for (int i = 0; i < n; i++) {
            if (s[i] != '0' && s[i] != '1') {
                return false;
            }
            source[i] = s[i] - '0';
        }
        return true;
    }

    bool valid_binary(const vector<int> &bits) {
        for (int x : bits) {
            if (x != 0 && x != 1) {
                return false;
            }
        }
        return true;
    }

    bool valid_attachment(const vector<int> &attachment, int n, string &reason) {
        if ((int)attachment.size() > 2 * n) {
            reason = "do dai attachment vuot qua 2N";
            return false;
        }
        if (!valid_binary(attachment)) {
            reason = "attachment khong phai day nhi phan";
            return false;
        }
        return true;
    }

    bool valid_source(const vector<int> &source, int n, string &reason) {
        if ((int)source.size() != n) {
            reason = "retrieve tra ve sai do dai";
            return false;
        }
        if (!valid_binary(source)) {
            reason = "retrieve tra ve day khong nhi phan";
            return false;
        }
        return true;
    }

    bool solve_case(const vector<int> &source, int n, int &used_k, string &reason) {
        vector<int> attachment = A::get_attachment(source);
        if (!valid_attachment(attachment, n, reason)) {
            return false;
        }
        used_k = (int)attachment.size();

        vector<int> data = source;
        data.insert(data.end(), attachment.begin(), attachment.end());

        for (int pos = -1; pos < (int)data.size(); pos++) {
            vector<int> corrupted = data;
            if (pos != -1) {
                corrupted[pos] ^= 1;
            }

            vector<int> recovered = B::retrieve(corrupted);
            if (!valid_source(recovered, n, reason)) {
                reason += " tai vi tri loi " + to_string(pos);
                return false;
            }
            if (recovered != source) {
                reason = "khong khoi phuc dung source tai vi tri loi " + to_string(pos);
                return false;
            }
        }

        return true;
    }

    Verdict solve() {
        int n, t;
        if (!(cin >> n >> t)) {
            return {false, 0, 0, 0, 0, "khong doc duoc N va T"};
        }
        if ((n != 63 && n != 255) || t <= 1 || t >= 20000) {
            return {false, 0, t, 0, 0, "N hoac T nam ngoai gioi han"};
        }

        int passed = 0;
        int max_k = 0;
        for (int tc = 0; tc < t; tc++) {
            vector<int> source;
            if (!read_source(n, source)) {
                return {false, passed, t, max_k, tc + 1, "scenario khong hop le"};
            }

            string reason;
            int used_k = 0;
            if (!solve_case(source, n, used_k, reason)) {
                return {false, passed, t, max_k, tc + 1, reason};
            }

            max_k = max(max_k, used_k);
            passed++;
        }

        return {true, passed, t, max_k, 0, ""};
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    jury::Verdict verdict = jury::solve();
    if (verdict.ok) {
        cout << "OK\n";
        cout << verdict.passed << ' ' << verdict.total << '\n';
        cout << verdict.max_k << '\n';
    } else {
        cout << "WA\n";
        cout << verdict.passed << ' ' << verdict.total << '\n';
        cout << verdict.failed_case << '\n';
        cout << verdict.max_k << '\n';
        cout << verdict.reason << '\n';
    }
    return 0;
}

Định dạng input của bộ chấm cục bộ

Dòng 1: hai số nguyên ~N~ và ~T~.
~T~ dòng tiếp theo: mỗi dòng là một xâu nhị phân độ dài ~N~, biểu diễn một source.

Định dạng output

Nếu vượt qua toàn bộ scenario, chương trình in:

OK
so_scenario_dung tong_so_scenario
max_k

Nếu có lỗi, chương trình in:

WA
so_scenario_dung tong_so_scenario
chi_so_scenario_loi_dau_tien
max_k_hien_tai
ly_do

Ràng buộc

~N \in \{63, 255\}~
~1 < T < 20000~
source[i] luôn là ~0~ hoặc ~1~

Các scenario là độc lập với nhau. Chiến lược của bạn không được phụ thuộc vào thứ tự xuất hiện của scenario.

Subtasks

Có ~2~ subtasks:

(60 điểm) ~N = 63~
(40 điểm) ~N = 255~

Nếu sai ở bất kỳ scenario nào trong subtask thì điểm subtask bằng ~0~.

Nếu đúng toàn bộ, gọi ~Q~ là giá trị lớn nhất của ~K~ trong mọi scenario thuộc subtask đó.

Bảng điểm cho ~N = 63~

~Q > 126~: ~0~ điểm
~64 < Q \le 126~: ~3~ điểm
~40 < Q \le 64~: ~9~ điểm
~20 < Q \le 40~: ~18~ điểm
~16 < Q \le 20~: ~30~ điểm
~12 < Q \le 16~: ~36~ điểm
~7 < Q \le 12~: ~48~ điểm
~Q \le 7~: ~60~ điểm

Bảng điểm cho ~N = 255~

~Q > 510~: ~0~ điểm
~256 < Q \le 510~: ~2~ điểm
~140 < Q \le 256~: ~6~ điểm
~35 < Q \le 140~: ~12~ điểm
~32 < Q \le 35~: ~20~ điểm
~16 < Q \le 32~: ~24~ điểm
~9 < Q \le 16~: ~32~ điểm
~Q \le 9~: ~40~ điểm

Ví dụ

Input

63 2
000000000000000000000000000000000000000000000000000000000000000
101010101010101010101010101010101010101010101010101010101010101

Output

OK
2 2
7

Ghi chú

Ví dụ trên chỉ minh họa format I/O của bộ chấm cục bộ. Nếu chương trình in OK với max_k = 7 trên subtask ~N = 63~, checker sẽ cho điểm tối đa của subtask này.

testestset

Nộp bài

Time limit: 1.0 / Memory limit: 256M

Point: 100

Trong trường hợp đề bài hiển thị không chính xác, bạn có thể tải đề bài tại đây: Đề bài

https://oj.uz/problem/view/IOI20_stations

Machine

Nộp bài

Time limit: 1.0 / Memory limit: 256M

Point: 100

Alice và Bob là hai nhà khảo cổ. Alice tìm thấy bản thiết kế của một cỗ máy cổ, còn Bob tìm thấy chính cỗ máy đó.

Cỗ máy gồm ~N~ thiết bị mắc nối tiếp theo một hàng. Mỗi thiết bị thuộc một trong ba loại X, Y, Z. Từ trái sang phải, các thiết bị được đánh số từ ~0~ đến ~N-1~, và loại của thiết bị ~i~ là ~S_i~.

Bob muốn tháo toàn bộ các thiết bị ra khỏi cỗ máy, từng cái một. Tuy nhiên, thứ tự atháo là rất quan trọng.

Good Removal

Giả sử tại một thời điểm nào đó, ba thiết bị ~x < y < z~ vẫn chưa bị tháo, với:

~S_x = X~
~S_y = Y~
~S_z = Z~
mọi thiết bị giữa ~x~ và ~y~ đã bị tháo
mọi thiết bị giữa ~y~ và ~z~ đã bị tháo

Khi đó, nếu Bob tháo thiết bị ~y~, thao tác này được gọi là một good removal.

Mọi cách tháo khác đều không phải good removal.

Bob cần tháo hết ~N~ thiết bị sao cho số lượng good removals là lớn nhất có thể. Nhưng Bob không phân biệt được loại của từng thiết bị.

Alice biết toàn bộ dãy ~S~, nên cô ấy sẽ gửi cho Bob một dãy bit để hướng dẫn. Mục tiêu là:

Bob vẫn đạt được số good removals tối đa.
Số bit mà Alice gửi là nhỏ nhất có thể.

Nhiệm vụ

Bạn cần cài đặt hai thủ tục:

namespace Alice {
    std::vector<int> send_bits(int N, std::vector<char> S);
}

namespace Bob {
    std::vector<int> removal_order(int N, std::vector<int> A);
}

Alice::send_bits trả về dãy bit Alice gửi cho Bob.
Bob::removal_order nhận lại dãy bit đó và trả về thứ tự Bob sẽ tháo các thiết bị.

Ý nghĩa các hàm

`Alice::send_bits`

N là số thiết bị.
S là mảng độ dài ~N~, mỗi phần tử là X, Y hoặc Z.
Hàm phải trả về một mảng nhị phân A.
Mỗi phần tử của A phải là ~0~ hoặc ~1~.
Độ dài của A, ký hiệu là ~L~, không được vượt quá ~200000~.

`Bob::removal_order`

N là số thiết bị.
A là dãy bit mà Alice đã gửi.
Hàm phải trả về một hoán vị của các số từ ~0~ đến ~N-1~.
Thứ tự này chính là thứ tự Bob tháo các thiết bị.

Lưu ý chấm

HNOJ không hỗ trợ chấm bài này dưới dạng hai chương trình riêng biệt, nên file mẫu sol.cpp đã gộp cả hai phía vào cùng một chương trình.

Vậy nên bạn sẽ được cung cấp một khung code như sau. Chỉ code trong namespace Alice và namespace Bob. Không được dùng biến toàn cục để truyền thông tin trực tiếp giữa hai namespace.

#include <algorithm>
#include <iostream>
#include <string>
#include <vector>
using namespace std;

namespace Alice {
    vector<int> send_bits(int N, vector<char> S) {
        (void)N;
        (void)S;
        // Hoan thien ham nay.
        // Khong duoc dung bien toan cuc de truyen thong tin sang namespace Bob.
        return {};
    }
}

namespace Bob {
    vector<int> removal_order(int N, vector<int> A) {
        (void)N;
        (void)A;
        // Hoan thien ham nay.
        return {};
    }
}

namespace jury {
    const int MAX_L = 200000;

    struct Verdict {
        bool ok;
        int passed;
        int total;
        int max_l;
        int failed_case;
        string reason;
    };

    bool read_case(int &n, vector<char> &s) {
        string str;
        if (!(cin >> n >> str)) {
            return false;
        }
        if ((int)str.size() != n) {
            return false;
        }
        s.assign(str.begin(), str.end());
        for (char c : s) {
            if (c != 'X' && c != 'Y' && c != 'Z') {
                return false;
            }
        }
        return true;
    }

    bool valid_bits(const vector<int> &bits) {
        for (int x : bits) {
            if (x != 0 && x != 1) {
                return false;
            }
        }
        return true;
    }

    bool valid_order(const vector<int> &order, int n) {
        if ((int)order.size() != n) {
            return false;
        }
        vector<int> seen(n, 0);
        for (int x : order) {
            if (x < 0 || x >= n || seen[x]) {
                return false;
            }
            seen[x] = 1;
        }
        return true;
    }

    int target_good_removals(const vector<char> &s) {
        int n = (int)s.size();
        int first_x = -1;
        for (int i = 0; i < n; i++) {
            if (s[i] == 'X') {
                first_x = i;
                break;
            }
        }
        if (first_x == -1) {
            return 0;
        }

        int ans = 0;
        int segment_y_runs = 0;
        bool in_y_run = false;
        for (int i = first_x + 1; i < n; i++) {
            if (s[i] == 'Y') {
                if (!in_y_run) {
                    segment_y_runs++;
                    in_y_run = true;
                }
            } else {
                in_y_run = false;
            }

            if (s[i] == 'Z' && (i == n - 1 || s[i + 1] != 'Z')) {
                ans += segment_y_runs;
                segment_y_runs = 0;
                in_y_run = false;
            }
        }
        return ans;
    }

    int count_good_removals(const vector<char> &s, const vector<int> &order) {
        int n = (int)s.size();
        vector<int> prv(n), nxt(n);
        for (int i = 0; i < n; i++) {
            prv[i] = i - 1;
            nxt[i] = i + 1;
        }
        nxt[n - 1] = -1;

        int good = 0;
        for (int y : order) {
            int l = prv[y];
            int r = nxt[y];
            if (s[y] == 'Y' && l != -1 && r != -1 && s[l] == 'X' && s[r] == 'Z') {
                good++;
            }
            if (l != -1) {
                nxt[l] = r;
            }
            if (r != -1) {
                prv[r] = l;
            }
        }
        return good;
    }

    bool solve_case(const vector<char> &s, int &used_l, string &reason) {
        int n = (int)s.size();

        vector<int> bits = Alice::send_bits(n, s);
        if (!valid_bits(bits)) {
            reason = "Alice::send_bits tra ve day khong nhi phan";
            return false;
        }
        if ((int)bits.size() > MAX_L) {
            reason = "so bit gui di vuot qua 200000";
            return false;
        }
        used_l = (int)bits.size();

        vector<int> order = Bob::removal_order(n, bits);
        if (!valid_order(order, n)) {
            reason = "Bob::removal_order khong phai hoan vi hop le";
            return false;
        }

        int contestant = count_good_removals(s, order);
        int target = target_good_removals(s);
        if (contestant != target) {
            reason = "so good removals khong toi uu";
            return false;
        }
        return true;
    }

    Verdict solve() {
        int t;
        if (!(cin >> t)) {
            return {false, 0, 0, 0, 0, "khong doc duoc T"};
        }
        if (t <= 0) {
            return {false, 0, t, 0, 0, "T phai duong"};
        }

        int passed = 0;
        int max_l = 0;
        for (int tc = 0; tc < t; tc++) {
            int n;
            vector<char> s;
            if (!read_case(n, s)) {
                return {false, passed, t, max_l, tc + 1, "scenario khong hop le"};
            }
            if (n < 3 || n > 100000) {
                return {false, passed, t, max_l, tc + 1, "N nam ngoai gioi han"};
            }

            string reason;
            int used_l = 0;
            if (!solve_case(s, used_l, reason)) {
                return {false, passed, t, max_l, tc + 1, reason};
            }

            max_l = max(max_l, used_l);
            passed++;
        }

        return {true, passed, t, max_l, 0, ""};
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    jury::Verdict verdict = jury::solve();
    if (verdict.ok) {
        cout << "OK\n";
        cout << verdict.passed << ' ' << verdict.total << '\n';
        cout << verdict.max_l << '\n';
    } else {
        cout << "WA\n";
        cout << verdict.passed << ' ' << verdict.total << '\n';
        cout << verdict.failed_case << '\n';
        cout << verdict.max_l << '\n';
        cout << verdict.reason << '\n';
    }
    return 0;
}

Định dạng input của bộ chấm cục bộ

Dòng 1: số nguyên ~T~.
Với mỗi scenario:
Dòng 1: số nguyên ~N~.
Dòng 2: xâu độ dài ~N~ chỉ gồm các ký tự X, Y, Z.

Định dạng output

Nếu vượt qua toàn bộ scenario, chương trình in:

OK
so_scenario_dung tong_so_scenario
max_l

Nếu có lỗi, chương trình in:

WA
so_scenario_dung tong_so_scenario
chi_so_scenario_loi_dau_tien
max_l_hien_tai
ly_do

Ràng buộc

~3 \le N \le 100000~
~S_i \in \{X, Y, Z\}~

Chấm điểm

Có ~2~ nhóm test trong package:

Test1 tới Test4: các scenario nhỏ với ~N \le 18~.
Test5 tới Test20: nhóm tổng quát.

Checker hoạt động như sau:

Nếu file chỉ chứa scenario với ~N \le 18~, bài được chấm nhị phân AC/WA.
Với file tổng quát, nếu số good removals đã tối ưu thì điểm phụ thuộc vào ~L = \max~ số bit Alice gửi trong file đó.

Với nhóm tổng quát, điểm được tính theo bảng:

Nếu ~160000 < L \le 200000~: ~25 + \left\lfloor 10 \cdot \frac{200000 - L}{40000} \right\rfloor~
Nếu ~100000 < L \le 160000~: ~35 + \left\lfloor 30 \cdot \frac{160000 - L}{60000} \right\rfloor~
Nếu ~70000 < L \le 100000~: ~65 + 30 \cdot \left(\frac{100000 - L}{30000}\right)^2~
Nếu ~L \le 70000~: ~95~

Ví dụ

Input

1
4
XYXZ

Output

OK
1 1
2

Ghi chú

Ví dụ trên chỉ minh hoạ format của bộ chấm cục bộ. max_l = 2 chỉ là một ví dụ về số bit gửi đi, không phải đáp án duy nhất.