JOI 2023 - Tuyển chọn mùa xuân - Ngày 4

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.

Vương quốc JOI có \(N\) hòn đảo, đánh số từ \(1\) đến \(N\). Mỗi đảo có một mức độ mất an ninh; mức độ mất an ninh của đảo \(i\) (\(1\le i\le N\)) là \(S_i\).

Phương tiện đi lại chủ yếu giữa các đảo là tàu. Có \(M\) con tàu, đánh số từ \(1\) đến \(M\). Tàu \(j\) (\(1\le j\le M\)) nối đảo \(A_j\) với đảo \(B_j\) và có thể được điều động khi cần. Có thể đi từ một đảo bất kỳ đến bất kỳ đảo nào khác bằng cách đi một số tàu.

Vương quốc dự định bổ sung tàu mới. Với mỗi tàu mới, có thể tùy ý chọn cặp đảo mà tàu nối.

Một ngày nọ, một tàu đang neo đậu bị tấn công. Thủ tướng K quyết định bổ sung tàu mới và yêu cầu các tàu phải tuân theo điều kiện an ninh:

• Khi một tàu neo tại đảo \(i\) (\(1\le i\le N\)), số nhân viên bảo vệ trên tàu phải ít nhất là \(S_i\).

Do thuê bảo vệ tốn kém, cần giảm thiểu tổng số nhân viên bảo vệ được thuê. Có thể ngừng sử dụng các tàu đang hoạt động, miễn vẫn có thể đi giữa mọi cặp đảo.

Gọi \(k\) là số tàu mới được bổ sung. Ta tổ chức hoạt động của các tàu theo các bước:

1. Với mỗi tàu mới trong số \(k\) tàu, chọn hai đảo mà tàu nối.
2. Chọn một số tàu, có thể bằng \(0\), để ngừng sử dụng. Được phép ngừng sử dụng cả tàu vừa bổ sung.
3. Với mỗi tàu còn lại, cho tàu neo tại một trong hai đảo mà nó nối và bố trí một số nhân viên bảo vệ lên tàu. Cách bố trí phải thỏa mãn điều kiện dưới đây.

Điều kiện: Với mọi cặp đảo \(u,v\) (\(1\le u,v\le N\)), phải có thể vận chuyển một hành khách từ đảo \(u\) đến đảo \(v\) bằng cách lặp lại các thao tác sau. Trong toàn bộ quá trình, điều kiện an ninh phải luôn được thỏa mãn.

• Cho hành khách hoặc nhân viên bảo vệ lên một tàu đang neo tại đảo nơi người đó đang ở.
• Cho hành khách hoặc nhân viên bảo vệ rời tàu, xuống đảo nơi tàu đang neo.
• Di chuyển một tàu từ đảo đang neo sang đảo còn lại mà tàu nối.

Ngân sách chỉ cho phép bổ sung tối đa \(Q\) tàu mới. Với mỗi \(k\) từ \(0\) đến \(Q\), thủ tướng K muốn biết số nhân viên bảo vệ ít nhất cần thuê nếu bổ sung \(k\) tàu mới.

Cho thông tin về các đảo, tuyến hoạt động của các tàu và số tàu mới có thể bổ sung, hãy tính số nhân viên bảo vệ ít nhất cần thuê cho từng giá trị \(k\).

Dữ liệu vào

Đọc từ đầu vào chuẩn theo định dạng:

N M Q
S_1 S_2 ... S_N
A_1 B_1
A_2 B_2
...
A_M B_M

Dữ liệu ra

Xuất \(Q+1\) dòng ra đầu ra chuẩn. Dòng thứ \(k+1\) (\(0\le k\le Q\)) chứa số nhân viên bảo vệ ít nhất cần thuê khi bổ sung \(k\) tàu mới.

Ràng buộc

• \(2\le N\le200\,000\).
• \(N-1\le M\le400\,000\).
• \(0\le Q\le200\,000\).
• \(1\le S_i\le10^9\) với \(1\le i\le N\).
• \(1\le A_j<B_j\le N\) với \(1\le j\le M\).
• \((A_x,B_x)\ne(A_y,B_y)\) với \(1\le x<y\le M\).
• Có thể đi từ một đảo bất kỳ đến bất kỳ đảo nào khác bằng cách đi một số tàu.
• Tất cả giá trị đầu vào đều là số nguyên.

Phân nhóm

Mọi nhóm đều tuân theo các ràng buộc chung ở trên.

1. \(12\) điểm: \(M=N-1\), \(Q=0\), \(S_i\le2\) với mọi \(1\le i\le N\), \(A_j=j\), \(B_j=j+1\) với mọi \(1\le j\le M\).
2. \(13\) điểm: \(M=N-1\), \(Q=0\), \(A_j=j\), \(B_j=j+1\) với mọi \(1\le j\le M\).
3. \(12\) điểm: \(M=N-1\), \(Q=0\).
4. \(13\) điểm: \(Q=0\).
5. \(8\) điểm: \(N\le16\).
6. \(18\) điểm: \(N\le3\,000\).
7. \(24\) điểm: Không có ràng buộc bổ sung.

Ví dụ

4 3 0
2 1 3 2
1 2
2 3
3 4

7

4 3 1
2 1 3 2
1 2
2 3
3 4

7
5

3 3 0
1 1 1
1 2
1 3
2 3

2

8 7 0
2 2 2 2 2 2 2 2
1 2
2 3
3 4
4 5
5 6
6 7
7 8

14

8 7 0
16 39 36 23 15 48 23 56
1 2
1 3
2 4
2 5
3 6
3 7
7 8

245

10 13 4
314 159 265 358 979 323 846 264 338 327
1 2
1 4
2 3
2 5
3 6
4 5
4 7
5 6
5 8
6 9
7 8
8 9
9 10

3139
2901
2722
2567
2461

Nguồn

JOI 2022/2023 Spring Training, Contest 4, bài Security Guard, tác giả 戸髙空.

Bản dịch tiếng Việt 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.

Thành phố JOI có một con đường rất dài, có thể xem như trục số thực. Mỗi vị trí trên đường được biểu diễn bằng một tọa độ thực. Dọc con đường có \(N\) điểm tham quan, đánh số từ \(1\) đến \(N\) theo thứ tự tọa độ tăng dần. Điểm tham quan thứ \(i\) (\(1\le i\le N\)) có tọa độ \(X_i\).

Bitaro sẽ ghé thăm tất cả các điểm tham quan. Vì phương châm sống của cậu là "tham lam", cậu lặp lại quy trình sau cho đến khi đã thăm hết:

• Gọi \(x\) là tọa độ hiện tại của Bitaro. Trong số các điểm chưa ghé thăm, chọn điểm \(i\) có khoảng cách \(|x-X_i|\) nhỏ nhất. Bitaro di chuyển đến tọa độ của điểm \(i\) và ghé thăm điểm đó. Nếu có nhiều điểm cùng đạt khoảng cách nhỏ nhất, cậu chọn điểm có tọa độ nhỏ nhất. Ở đây, \(|t|\) là giá trị tuyệt đối của \(t\).

Qua nhiều năm kinh nghiệm, Bitaro biết rằng quy trình này có thể khiến tổng quãng đường di chuyển dài hơn dự kiến. Tổng quãng đường phụ thuộc vào tọa độ xuất phát. Vì vậy, với mỗi tọa độ xuất phát trong \(Q\) lựa chọn \(S_1,S_2,\ldots,S_Q\), cậu muốn biết tổng quãng đường phải đi cho đến khi đã ghé thăm tất cả các điểm.

Cho thông tin về các điểm tham quan và các tọa độ xuất phát, hãy tính tổng quãng đường di chuyển của Bitaro với từng lựa chọn.

Dữ liệu vào

Đọc từ đầu vào chuẩn theo định dạng:

N
X_1 X_2 ... X_N
Q
S_1
S_2
...
S_Q

Dữ liệu ra

Xuất \(Q\) dòng ra đầu ra chuẩn. Dòng thứ \(j\) (\(1\le j\le Q\)) chứa tổng quãng đường Bitaro di chuyển nếu xuất phát tại tọa độ \(S_j\).

Ràng buộc

• \(1\le N\le200\,000\).
• \(1\le Q\le200\,000\).
• \(0\le X_i\le10^9\) với \(1\le i\le N\).
• \(X_i<X_{i+1}\) với \(1\le i\le N-1\).
• \(0\le S_j\le10^9\) với \(1\le j\le Q\).
• Tất cả giá trị đầu vào đều là số nguyên.

Phân nhóm

Mọi nhóm đều tuân theo các ràng buộc chung ở trên.

1. \(5\) điểm: \(Q=1\), \(N\le2\,000\).
2. \(10\) điểm: \(Q=1\).
3. \(30\) điểm: \(X_{i+1}-X_i\le100\) với mọi \(1\le i\le N-1\).
4. \(55\) điểm: Không có ràng buộc bổ sung.

Ví dụ

5
0 5 6 7 9
1
7

15

10
1 2 3 4 5 6 7 8 9 10
10
1
2
3
4
5
6
7
8
9
10

9
10
11
12
13
14
15
16
17
9

Nguồn

JOI 2022/2023 Spring Training, Contest 4, bài Bitaro's Travel, tác giả 米田寛峻 và 米田優峻.

Bản dịch tiếng Việt 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.