JOICup là chương trình truyền hình giải trí nổi tiếng của đài JOI. Chương trình đã bước vào vòng chung kết, nơi diễn ra trò chơi truyền tin. Chỉ một đội vượt qua vòng đầu được tham gia trò chơi; đội gồm hai người chơi Anna và Bruno.

Trong trò chơi, thông tin được truyền bằng một bảng gồm \(8\times8\) ô. Các hàng và các cột đều được đánh số từ \(0\) đến \(7\).

Anna và Bruno ở trong hai phòng riêng biệt, cách ly với nhau. Họ thực hiện \(Q\) thử thách. Thử thách thứ \(i\) (\(1\le i\le Q\)) diễn ra như sau:

1. Bitaro, người dẫn trò chơi, đưa cho Anna một tấm thẻ và một bảng \(8\times8\) ô. Trên thẻ có ba số nguyên \(X_i,Y_i,N_i\) (\(0\le X_i\le7\), \(0\le Y_i\le7\), \(1\le N_i\le43\)) và xâu \(S_i\) dài \(N_i\) chỉ gồm các ký tự A, B. Ban đầu, tất cả các ô đều màu trắng.
2. Anna tô từng ô trong số \(49\) ô có số hàng khác \(X_i\) và số cột khác \(Y_i\). Mỗi ô được tô màu xanh lam hoặc đỏ.
3. Anna đưa bảng cho Bitaro.
4. Bitaro tô từng ô trong số \(15\) ô có số hàng bằng \(X_i\) hoặc số cột bằng \(Y_i\). Mỗi ô được tô màu xanh lam hoặc đỏ. Việc này diễn ra trong một phòng mà cả Anna lẫn Bruno đều không nhìn thấy.
5. Bitaro đưa cho Bruno một tấm thẻ và bảng đã tô. Trên thẻ chỉ có số nguyên \(N_i\).
6. Bruno viết một xâu lên giấy. Nếu xâu đó trùng với \(S_i\), Anna và Bruno thắng thử thách.

Luồng trao đổi trong mỗi thử thách được minh họa dưới đây. Các số từ \(1\) đến \(6\) trong hình tương ứng với sáu bước vừa mô tả.

Hãy viết các chương trình cài đặt chiến lược của Anna và Bruno để thắng trò chơi truyền tin. Cách tính điểm được mô tả trong phần Phân nhóm.

Chi tiết cài đặt

Trên hệ thống này, cần nộp một tệp battle.cpp chứa cả hai hàm Anna và Bruno, có chỉ thị #include "battle.h". Các giao diện và cách tính điểm bên dưới không thay đổi so với đề gốc.

Trong tệp battle.cpp, cài đặt chiến lược của Anna bằng hàm:

void Anna(int X, int Y, int N, std::string S);

Hàm được gọi \(Q\) lần. Lần gọi thứ \(i\) (\(1\le i\le Q\)) tương ứng với các bước \(1,2,3\) của thử thách thứ \(i\). Các tham số X, Y, N, S lần lượt là \(X_i,Y_i,N_i,S_i\) ghi trên thẻ Anna nhận ở bước \(1\).

Trong mỗi lần gọi Anna, phải gọi hàm sau đúng \(49\) lần, mỗi ô có hàng khác X và cột khác Y đúng một lần:

void Paint(int a, int b, int c);

• a, b là số hàng và số cột của ô Anna tô. Phải có \(0\le a\le7\), \(0\le b\le7\), \(a\ne X\), \(b\ne Y\); nếu không, bị chấm Wrong Answer [1].
• c biểu diễn màu: 0 là xanh lam, 1 là đỏ. Phải có \(0\le c\le1\); nếu không, bị chấm Wrong Answer [2].
• Nếu gọi Paint nhiều hơn một lần với cùng cặp (a, b), bị chấm Wrong Answer [3].
• Khi Anna kết thúc, nếu số lần gọi Paint khác \(49\), bị chấm Wrong Answer [4].

Trong cùng tệp battle.cpp, cài đặt chiến lược của Bruno bằng hàm:

std::string Bruno(int N, std::vector<std::vector<int>> T);

Hàm được gọi sau mỗi lần Anna tô xong bảng, tổng cộng \(Q\) lần. Lần gọi thứ \(i\) (\(1\le i\le Q\)) tương ứng với các bước \(5,6\) của thử thách thứ \(i\).

• N là số nguyên \(N_i\) trên thẻ Bruno nhận ở bước \(5\).
• T là mảng hai chiều kích thước \(8\times8\) mô tả bảng Bruno nhận ở bước \(5\). Ô hàng a, cột b (\(0\le a,b\le7\)) màu xanh lam nếu T[a][b] = 0, màu đỏ nếu T[a][b] = 1.
• Giá trị trả về là xâu Bruno viết lên giấy.
• Nếu xâu trả về dài từ \(44\) ký tự trở lên, bị chấm Wrong Answer [5].
• Mỗi ký tự của xâu trả về phải là A hoặc B; nếu không, bị chấm Wrong Answer [6].

Lưu ý quan trọng

Có thể cài đặt hàm phụ trợ hoặc sử dụng biến toàn cục. Tệp nộp sẽ được liên kết với trình chấm thành một tệp thực thi. Tất cả biến toàn cục và hàm phụ trợ phải được khai báo trong không gian tên vô danh để tránh xung đột với trình chấm; các phần cài đặt của Anna và Bruno trong cùng tệp cũng phải tránh trùng tên. Khi chấm, tệp thực thi chạy thành hai tiến trình, một cho Anna và một cho Bruno; hai tiến trình không thể chia sẻ biến toàn cục.

Chương trình 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. Có thể 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 hỗ trợ một tệp nộp trong phần đính kèm chứa trình chấm mẫu chính thức grader.cpp, tệp mẫu battle.cpp, các tệp khai báo battle.h, Anna.h, Bruno.h, và hai đầu vào mẫu sample-01.txt, sample-02.txt. Giữ các tệp trong cùng thư mục rồi biên dịch bằng lệnh:

g++ -std=gnu++17 -O2 -o grader grader.cpp battle.cpp

Cũng có thể chạy compile.sh trong gói hỗ trợ. Nếu biên dịch thành công, tệp thực thi grader được tạo ra.

Trình chấm thật khác trình chấm mẫu. Đặc biệt, Bitaro không nhất thiết chọn màu cho các ô một cách ngẫu nhiên. Trình chấm mẫu 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

Trình chấm mẫu đọc đầu vào chuẩn theo định dạng:

Q
X_1 Y_1 N_1 S_1
X_2 Y_2 N_2 S_2
...
X_Q Y_Q N_Q S_Q

Dữ liệu ra

Trình chấm mẫu ghi thông tin sau ra đầu ra chuẩn:

• Nếu chương trình không bị chấm sai, ghi giá trị \(L^*\), chẳng hạn Accepted: 28. Định nghĩa \(L^*\) nằm trong phần Phân nhóm.
• Nếu bị chấm sai, ghi loại lỗi, chẳng hạn Wrong Answer [1].

Nếu chương trình đồng thời thỏa mãn nhiều điều kiện bị chấm sai, trình chấm mẫu chỉ báo một loại lỗi.

Trong trình chấm mẫu, các màu Bitaro chọn được xác định bằng số giả ngẫu nhiên và không thay đổi giữa các lần chạy với cùng hạt giống. Có thể thay đổi hạt giống bằng đối số nguyên đầu tiên, chẳng hạn:

./grader 2023

Ràng buộc

• \(1\le Q\le20\,000\).
• \(0\le X_i\le7\) với \(1\le i\le Q\).
• \(0\le Y_i\le7\) với \(1\le i\le Q\).
• \(1\le N_i\le43\) với \(1\le i\le Q\).
• \(Q,X_i,Y_i,N_i\) đều là số nguyên.
• \(S_i\) (\(1\le i\le Q\)) là xâu dài \(N_i\) chỉ gồm các ký tự A, B.

Phân nhóm

Bài này tính điểm theo độ dài truyền tin, không chia thành các nhóm cộng điểm độc lập.

Nếu chương trình bị bất kỳ lỗi Wrong Answer [1] đến Wrong Answer [6], hoặc bất kỳ lỗi thực thi nào như quá thời gian (TLE), quá bộ nhớ (MLE), kết thúc bất thường, v.v. trong bất kỳ bộ kiểm thử nào, điểm của toàn bài là \(0\), bất kể kết quả thắng các thử thách trong những bộ kiểm thử khác.

Nếu không có các lỗi trên, trong mỗi bộ kiểm thử, xét giá trị lớn nhất \(L\) sao cho Anna và Bruno thắng tất cả thử thách có \(N_i\le L\). Nếu thắng tất cả thử thách trong bộ kiểm thử đó, đặt \(L=43\). Gọi \(L^*\) là giá trị nhỏ nhất của các giá trị \(L\) trên tất cả bộ kiểm thử của bài. Điểm được tính theo bảng sau:

Ví dụ giao tiếp

Ví dụ 1

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

2
0 0 1 B
5 7 8 AAAABBBB

Lời gọi và giá trị trả về

Tham số T trong các lời gọi Bruno được lược bỏ, giống bảng minh họa của đề.

Giải thích

Có \(Q=2\) thử thách:

• Thử thách thứ nhất có \(X_1=0\), \(Y_1=0\), \(N_1=1\), \(S_1=\texttt{B}\). Anna tô \(49\) ô có hàng khác \(0\) và cột khác \(0\).
• Thử thách thứ hai có \(X_2=5\), \(Y_2=7\), \(N_2=8\), \(S_2=\texttt{AAAABBBB}\). Anna tô \(49\) ô có hàng khác \(5\) và cột khác \(7\).

Chẳng hạn, nếu gọi Paint(0, 2, 1) trong thử thách đầu tiên, chương trình bị chấm Wrong Answer [1] vì chỉ định một ô ở hàng \(0\).

Ví dụ 2

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

30
3 1 1 A
1 4 1 A
6 6 2 AA
1 1 2 BB
3 1 3 BAB
7 4 3 AAB
6 4 4 BAAB
6 7 4 BABA
3 3 5 BABBA
1 5 5 ABBBA
4 3 6 ABBBBB
2 1 6 ABAAAA
6 0 7 AAABABA
6 6 7 BBABBAA
0 4 8 AABAABAB
2 1 8 AABBBBBA
2 0 9 BABABBAAA
1 5 9 BBAAABABB
6 7 10 BAAABAAABB
1 7 10 BBBBBBBABA
2 6 12 AABAABABABAB
3 4 15 BBAABAAAABABAAB
5 6 18 BAAAABBABABBBABBAB
7 0 22 BABBAABAAABBABBBBBBABA
2 0 26 AAAABBABBAAAAABABABBAABAAA
0 7 30 AAABBBAAABAABBBBAABBAAABBBABBB
2 7 34 BABAABBAABABBABAABBABBABAABBBBABBB
2 5 38 BBBBAABAABAABABABBBBBAAABBABAAABAAABBB
5 2 41 AABABBAAABBABAAAABBABABBAAAAAABBABBABBABA
1 0 43 AABBABBBBABABBBABBBBAAAAAABABAAABBBAABBAAAB

Nguồn

JOI 2022/2023 Spring Training, Contest 4, bài The Last Battle, tác giả 米田寛峻 và 米田優峻.

Bản dịch tiếng Việt và hình từ đề của JCIOI (Ủy ban Olympic Tin học Quốc tế Nhật Bản), theo giấy phép CC BY-SA 4.0.