Anna và Bruno là hai nhà khảo cổ học đang khai quật tàn tích của vương quốc IOI. Tại khu di tích A, Anna tìm thấy bản thiết kế một cỗ máy cổ. Tại khu di tích B, Bruno tìm thấy chính cỗ máy đó.

Cỗ máy gồm \(N\) thiết bị gắn thành một hàng trên dây điện. Có ba loại thiết bị, gọi là X, Y, Z. Từ trái sang phải, các thiết bị được đánh số từ \(0\) đến \(N-1\). Loại của thiết bị \(i\) là \(S_i\), một trong ba ký tự X, Y, Z.

Cỗ máy quá lớn, nên Bruno quyết định tháo từng thiết bị ra. Tuy nhiên, chúng tương tác với nhau qua dây điện, nên thứ tự tháo cần được lựa chọn cẩn thận.

Ta định nghĩa lần tháo tốt như sau:

• Giả sử các thiết bị \(x,y,z\) (\(0\le x<y<z\le N-1\)) chưa bị tháo, \(S_x=\mathrm{X}\), \(S_y=\mathrm{Y}\), \(S_z=\mathrm{Z}\). Đồng thời, mọi thiết bị có chỉ số \(j\) với \(x<j<y\) đã bị tháo, và mọi thiết bị có chỉ số \(k\) với \(y<k<z\) đã bị tháo. Nếu tất cả điều kiện này thỏa mãn, việc tháo thiết bị \(y\) được gọi là một lần tháo tốt.
• Mọi cách tháo một thiết bị khác đều không phải lần tháo tốt.

Bruno phải tháo cả \(N\) thiết bị sao cho số lần tháo tốt lớn nhất có thể. Nhưng ba loại thiết bị trông giống nhau nên Bruno không phân biệt được chúng.

Anna có bản thiết kế nên biết loại của từng thiết bị. Cô sẽ dùng máy phát để giúp Bruno bằng cách gửi một dãy ký tự, mỗi ký tự là \(0\) hoặc \(1\).

Hãy viết các chương trình thực hiện chiến lược của Anna và Bruno để đạt số lần tháo tốt lớn nhất có thể. Trong bài này, Anna gửi càng ít ký tự cho Bruno thì điểm càng cao.

Chi tiết cài đặt

Bạn cần nộp hai tệp.

Tệp Anna.cpp cài đặt chiến lược của Anna, nạp Anna.h bằng chỉ thị #include và cài đặt hàm:

void Anna(int N, std::vector<char> S);

Hàm được gọi đúng một lần lúc bắt đầu mỗi bộ dữ liệu. N là số thiết bị; S là mảng độ dài \(N\), trong đó S[i] là loại thiết bị \(i\), bằng 'X', 'Y' hoặc 'Z'.

Anna có thể gọi hàm sau để gửi một ký tự cho Bruno:

void Send(int a);

• a phải bằng \(0\) hoặc \(1\); nếu không, chương trình bị chấm Wrong Answer [1].
• Không được gọi Send quá \(200000\) lần; nếu vượt quá thì bị chấm Wrong Answer [2].

Tệp Bruno.cpp cài đặt chiến lược của Bruno, nạp Bruno.h bằng chỉ thị #include và cài đặt:

void Bruno(int N, int L, std::vector<int> A);

Sau lời gọi Anna, hàm này được gọi đúng một lần. N là số thiết bị; L là số ký tự Anna đã gửi; A là mảng độ dài \(L\) chứa các ký tự đó theo đúng thứ tự A[0], A[1], ..., A[L-1]. Mỗi phần tử là \(0\) hoặc \(1\).

Bruno có thể gọi hàm sau để chỉ ra thứ tự tháo:

void Remove(int d);

• d là chỉ số thiết bị được tháo. Phải có \(0\le d\le N-1\); nếu không, bị chấm Wrong Answer [3].
• Không được gọi Remove với cùng một giá trị d nhiều lần; nếu không, bị chấm Wrong Answer [4].
• Phải gọi Remove đúng \(N\) lần. Khi Bruno kết thúc, nếu số lời gọi khác \(N\) thì bị chấm Wrong Answer [5].
• Sau khi tháo cả \(N\) thiết bị, số lần tháo tốt phải lớn nhất có thể. Nếu không đạt điều này, bị chấm Wrong Answer [6].

Lưu ý quan trọng

• Bạn có thể viết thêm hàm nội bộ hoặc dùng biến toàn cục. Hai tệp nộp được biên dịch cùng grader thành một tệp thực thi. Mọi hàm nội bộ và biến toàn cục cần nằm trong namespace không tên để tránh xung đột với tệp khác. Khi chấm thực tế, Anna và Bruno chạy trong hai tiến trình và không thể chia sẻ biến toàn cục.
• Chương trình không được dùng đầu vào chuẩn, đầu ra chuẩn hoặc trao đổi với các tệp khác bằng bất kỳ cách nào. Được phép ghi thông tin gỡ lỗi ra đầu ra lỗi chuẩn.

Biên dịch và chạy thử

Trang cuộc thi cung cấp gói gồm grader mẫu và các tệp chương trình mẫu. Đặt grader.cpp, Anna.cpp, Bruno.cpp, Anna.h, Bruno.h trong cùng thư mục, rồi biên dịch:

g++ -std=gnu++17 -O2 -fsigned-char -o grader grader.cpp Anna.cpp Bruno.cpp

Nếu thành công, tệp thực thi grader được tạo. Grader thực tế khác grader mẫu. Grader mẫu chỉ chạy trong một tiến trình, đọc đầu vào chuẩn và ghi kết quả ra đầu ra chuẩn.

Dữ liệu vào

Grader mẫu đọc theo định dạng:

N
S_0 S_1 ... S_{N-1}

Hai ký tự \(S_i,S_{i+1}\) liên tiếp (\(0\le i\le N-2\)) được phân cách bằng một dấu cách.

Dữ liệu ra

Khi chương trình kết thúc bình thường, grader mẫu ghi:

• Nếu vi phạm một trong các lỗi Wrong Answer [1] đến Wrong Answer [5]: loại lỗi, chẳng hạn Wrong Answer [1].
• Nếu không: Accepted: L D, trong đó \(L\) là số lần gọi Send, còn \(D\) là số lần tháo tốt. Grader mẫu không kiểm tra tính tối ưu, tức không kiểm tra lỗi Wrong Answer [6]; đây là điểm khác với grader thực tế.

Nếu chương trình thỏa mãn nhiều loại lỗi trong các lỗi \(1\) đến \(5\), grader mẫu chỉ thông báo một loại.

Ràng buộc

• \(3\le N\le100000\).
• \(S_i\) là một trong các ký tự X, Y, Z với mọi \(0\le i\le N-1\).

Phân nhóm

• Nhóm 1 (5 điểm): \(N\le18\).
• Nhóm 2 (95 điểm): Không có ràng buộc bổ sung. Điểm được tính như dưới đây.

Gọi \(L\) là số lần gọi Send lớn nhất trên tất cả bộ dữ liệu của nhóm 2.

Ở đây, \(\lfloor x\rfloor\) là số nguyên lớn nhất không vượt quá \(x\).

Ví dụ giao tiếp

Ví dụ 1

Dữ liệu vào của trình chấm mẫu:

4
X Y X Z

Lời gọi hàm

Giải thích

Các thiết bị được tháo như sau:

1. Ban đầu, dãy thiết bị là X Y X Z.
2. Tháo thiết bị \(2\), dãy trở thành X Y - Z. Dấu - biểu thị vị trí đã tháo.
3. Tháo thiết bị \(1\), dãy trở thành X - - Z. Bộ \((x,y,z)=(0,1,3)\) thỏa mãn điều kiện, nên đây là lần tháo tốt.
4. Tháo thiết bị \(0\), dãy trở thành - - - Z.
5. Cuối cùng, tháo thiết bị \(3\), dãy trở thành - - - -.

Có \(1\) lần tháo tốt. Với đầu vào này, không thể có nhiều hơn \(1\) lần tháo tốt.

Ví dụ này thỏa mãn các nhóm \(1,2\).

Nguồn

JOI 2020/2021, kỳ thi tuyển chọn mùa xuân, ngày thi thứ 3. Đề của Ủy ban Olympic Tin học Nhật Bản (JCIOI). Bản dịch tiếng Việt theo giấy phép CC BY-SA 4.0.