Anna và Bruno, hai cao thủ cờ bạc, sắp tham gia một trò chơi với người chia bài D-taro. Trong trò chơi, Anna và Bruno ở hai phòng riêng biệt và chỉ có thể trao đổi thông tin thông qua D-taro.

Trò chơi sử dụng một hàng gồm \(N\) bóng đèn, được đánh số từ \(1\) đến \(N\) từ trái sang phải. Mỗi bóng đèn có thể phát sáng bằng một trong ba màu: đỏ, xanh lá cây hoặc xanh lam.

Đầu tiên, Anna chọn màu để bật từng bóng đèn. D-taro quy định một màu bị cấm cho mỗi bóng đèn, được mô tả bởi xâu \(S\) có độ dài \(N\). Gọi \(S_i\) là ký tự thứ \(i\) của \(S\) \((1 \le i \le N)\). Nếu \(S_i\) là R, bóng đèn \(i\) bị cấm màu đỏ; nếu là G, màu bị cấm là xanh lá cây; nếu là B, màu bị cấm là xanh lam. Anna không được bật bóng đèn bằng màu bị cấm của nó. Chẳng hạn, nếu \(S_1\) là R thì Anna không được bật bóng đèn \(1\) bằng màu đỏ. D-taro chỉ cho Anna biết các màu bị cấm, không cho Bruno biết.

Sau khi bật các bóng đèn, Anna chọn một số nguyên \(l\) thỏa mãn \(1 \le l \le \min(N,130)\) và báo cho D-taro. D-taro cho Bruno biết tổng số bóng đèn \(N\) và số nguyên \(l\) mà Anna đã chọn. Tiếp theo, họ chơi \(Q\) vòng như sau:

1. D-taro chọn số nguyên \(a_j\) trong đoạn từ \(1\) đến \(N-l+1\) và cho Bruno xem dãy màu của các bóng đèn \(a_j,a_j+1,\ldots,a_j+l-1\).
2. Dựa vào dãy màu được xem, Bruno trả lời D-taro một số nguyên. Nếu số này bằng \(a_j\) thì Anna và Bruno thắng vòng đó.

D-taro có thể lựa chọn \(a_1,a_2,\ldots,a_Q\) tùy theo dãy màu mà Anna bật và số nguyên \(l\) mà Anna chọn. Hãy cài đặt chương trình để Anna và Bruno thắng cả \(Q\) vòng.

Chi tiết cài đặt

Theo giao diện gốc, cần nộp hai tệp C++. Tệp thứ nhất là Anna.cpp, cài đặt chiến thuật của Anna và khai báo #include "Anna.h". Tệp này cài đặt hàm:

std::pair<std::string, int> anna(int N, std::string S);

Hàm được gọi đúng một lần lúc bắt đầu. Tham số N là số bóng đèn; S là xâu độ dài \(N\) biểu diễn các màu bị cấm do D-taro quy định. Hàm trả về một cặp gồm xâu \(t\) biểu diễn các màu Anna bật và số nguyên \(l\) Anna chọn. Ký tự thứ \(i\) của \(t\) cho biết màu bóng đèn \(i\): R là đỏ, G là xanh lá cây, B là xanh lam.

• Độ dài của \(t\) phải bằng \(N\); nếu không, chương trình bị chấm Wrong Answer [1].
• Mỗi ký tự của \(t\) phải là R, G hoặc B; nếu không, chương trình bị chấm Wrong Answer [2].
• Mỗi ký tự của \(t\) phải khác ký tự ở cùng vị trí trong \(S\); nếu không, chương trình bị chấm Wrong Answer [3].
• \(1 \le l \le \min(N,130)\); nếu không, chương trình bị chấm Wrong Answer [4].

Tệp thứ hai là Bruno.cpp, cài đặt chiến thuật của Bruno và khai báo #include "Bruno.h". Tệp này cài đặt các hàm:

void init(int N, int l);
int bruno(std::string u);

Hàm init được gọi đúng một lần lúc bắt đầu, với N là số bóng đèn và l là số nguyên Anna chọn.

Sau khi gọi init, hàm bruno được gọi \(Q\) lần, tương ứng với hai bước của mỗi vòng chơi. Tham số u là xâu độ dài \(l\) gồm các ký tự R, G, B, biểu diễn màu của các bóng đèn \(a_j,a_j+1,\ldots,a_j+l-1\). Ký tự \(u_k\) \((1 \le k \le l)\) cho biết màu của bóng đèn \(a_j+k-1\) theo cùng quy ước màu trên. Giá trị trả về là số nguyên Bruno trả lời. Giá trị này phải bằng \(a_j\); nếu không, chương trình bị chấm Wrong Answer [5].

Lưu ý quan trọng

Bạn được phép cài đặt các hàm phụ và khai báo biến toàn cục. Hai tệp nộp được liên kết cùng chương trình chấm thành một tệp thực thi. Mọi biến toàn cục và hàm nội bộ trong mỗi tệp cần được đặt trong không gian tên vô danh để tránh xung đột với các tệp khác. Khi chấm thật, tệp thực thi được chạy thành hai tiến trình riêng biệt, một cho Anna và một cho Bruno; hai phía không thể chia sẻ biến toàn cục.

Chương trình nộp không được sử dụng đầu vào chuẩn, đầu ra chuẩn hoặc giao tiếp với các tệp khác bằng bất kỳ cách nào. Bạn đượ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ử

Gói tệp đính kèm công khai chứa chương trình chấm mẫu grader.cpp, các tệp mẫu cần nộp và các tệp tiêu đề. Để thử chương trình theo giao diện gốc, đặt grader.cpp, Anna.cpp, Bruno.cpp, Anna.h, Bruno.h trong cùng thư mục và dùng lệnh sau, hoặc chạy compile.sh có trong gói:

g++ -std=gnu++20 -O2 -o grader grader.cpp Anna.cpp Bruno.cpp

Nếu biên dịch thành công, tệp thực thi grader được tạo ra. Chương trình chấm mẫu khác chương trình chấm thật: chương trình mẫu chạy trong một tiến trình duy nhất, đọc đầu vào chuẩn và ghi kết quả ra đầu ra chuẩn; thông báo lỗi đọc dữ liệu có thể được ghi ra đầu ra lỗi chuẩn.

Dữ liệu vào

Đây là định dạng đầu vào của chương trình chấm mẫu, không phải dữ liệu mà chương trình nộp tự đọc:

N
S
Q
a_1 a_2 ... a_Q

Khác với chương trình chấm thật, chương trình chấm mẫu cần biết trước các vị trí cố định. Số \(a_j\) \((1 \le j \le Q)\) là vị trí D-taro chọn ở vòng thứ \(j\). Với \(l\) do chương trình của Anna chọn, dữ liệu chạy thử phải thỏa mãn \(1 \le a_j \le N-l+1\).

Dữ liệu ra

Chương trình chấm mẫu in kết quả ra đầu ra chuẩn. Nếu trả lời đúng, nó in số nguyên \(l\) mà Anna chọn, chẳng hạn Accepted: 130. Nếu trả lời sai, nó in loại lỗi, chẳng hạn Wrong Answer [1]. Nếu đồng thời vi phạm nhiều điều kiện, chương trình chấm mẫu chỉ báo một loại lỗi. Chương trình nộp không tự in các thông báo này.

Khi chấm thật, các vị trí \(a_1,a_2,\ldots,a_Q\) được chọn dựa trên dãy màu Anna bật và số nguyên \(l\), nhưng không phụ thuộc vào những câu trả lời của Bruno.

Ràng buộc

• \(1 \le N \le 500\,000\).
• \(1 \le Q \le 10\,000\).
• \(S\) có độ dài \(N\) và chỉ gồm các ký tự R, G, B.
• \(N,Q\) là số nguyên.

Phân nhóm

• Nhóm 1 (5 điểm): \(N \le 131\).
• Nhóm 2 (5 điểm): \(N \le 250\).
• Nhóm 3 (5 điểm): \(N \le 380\).
• Nhóm 4 (15 điểm): \(N \le 7\,000\).
• Nhóm 5 (70 điểm): Không có ràng buộc bổ sung. Điểm được tính theo quy tắc dưới đây.

Đối với nhóm \(5\), gọi \(l^*\) là giá trị lớn nhất của \(l\) do Anna chọn trong tất cả bộ dữ liệu của nhóm. Nếu có bất kỳ bộ dữ liệu nào bị chấm Wrong Answer [1] đến Wrong Answer [5], vượt giới hạn thời gian, vượt giới hạn bộ nhớ hoặc gặp lỗi khi chạy, điểm của cả nhóm bằng \(0\). Nếu đúng tất cả bộ dữ liệu, điểm của nhóm là:

Ví dụ giao tiếp

Ví dụ 1

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

8
RGGBRBBG
2
3 1

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

Bảng sau mô tả các lời gọi hàm và giá trị trả về trong một lần tương tác mẫu, không phải văn bản mà chương trình nộp in ra:

Giải thích

Anna nhận \(N=8\) và xâu màu bị cấm RGGBRBBG. Anna chọn xâu màu bật BBRGBGRR và \(l=5\), rồi báo cho D-taro. Sau đó D-taro cho Bruno biết \(N=8\) và \(l=5\).

Ở vòng thứ nhất, D-taro chọn \(a_1=3\). Bruno nhận xâu RGBGR, là màu của các bóng đèn \(3,4,5,6,7\), và trả lời \(3\), đúng bằng \(a_1\).

Ví dụ này thỏa mãn ràng buộc của tất cả các nhóm. Tệp sample-01-in.txt trong gói tải về tương ứng với ví dụ này.

Nguồn

Nguồn: JOI 2023/2024, kỳ thi tuyển chọn mùa xuân, ngày thi thứ hai (22/03/2024). Đề bài 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.