JOI 2026 - Chung kết - Cuộc thi 2

Azzurro và Bordeaux đến một sòng bạc ở Ý và quyết định chơi trò chơi do người chia bài Chiaro đề xuất. Hai người được đưa vào hai phòng riêng biệt và chơi \(Q\) lượt. Trong mỗi lượt, Azzurro hành động trước, rồi đến Bordeaux: Azzurro nhận chuỗi \(S\) gồm A và B, độ dài \(L\), và tô xanh hoặc đỏ mọi ô của bảng \(8\times8\); Chiaro bí mật chọn một đường đi từ góc trên trái đến góc dưới phải, chỉ đi sang phải hoặc đi xuống, rồi đảo màu mọi ô trên đường đó; sau đó Bordeaux nhận bảng đã bị đảo màu và phải khôi phục \(S\).

Đây là bài Communication với hai tiến trình cô lập. Submission C++ của bạn phải cài đặt cả hai hàm dưới đây trong cùng một tệp; hai phía Azzurro và Bordeaux chạy trong hai tiến trình cô lập, không chia sẻ trạng thái với nhau. Không dùng standard input, standard output hoặc tệp khác; chỉ được ghi debug vào standard error.

std::vector<std::vector<int>> Azzurro(int N, int L, std::string S);
std::string Bordeaux(int N, int L, std::vector<std::vector<int>> T);

• Azzurro trả ma trận \(N\times N\) chỉ gồm 0 và 1; 0 là xanh, 1 là đỏ.
• Bordeaux trả chuỗi chỉ gồm A và B, đúng độ dài \(L\).

Các hàng và cột được đánh số từ \(0\) đến \(N-1\), lần lượt từ trên xuống dưới và từ trái sang phải. Mỗi đường đi của Chiaro bắt đầu ở \((0,0)\), kết thúc ở \((N-1,N-1)\) và mỗi bước chỉ đến ô kề ngay bên phải hoặc ngay phía dưới. Cả ô đầu và ô cuối đều bị đảo màu.

Ở lượt \(i\), Azzurro nhận \(N\), độ dài \(L_i\), chuỗi \(S_i\) và bảng ban đầu toàn màu trắng; sau đó phải tô mọi ô thành xanh hoặc đỏ. Bordeaux nhận \(N\), \(L_i\) và bảng sau khi Chiaro đảo màu, nhưng không nhận \(S_i\) hay đường đi. Mục tiêu là Bordeaux trả lại đúng chuỗi \(S_i\).

Trong Bordeaux, T[r][c] là màu của ô \((r,c)\): \(0\) là xanh và \(1\) là đỏ. Trả về ma trận sai kích thước hoặc có phần tử khác \(0,1\) bị chấm Wrong Answer [1]; trả về chuỗi sai độ dài hoặc có ký tự ngoài A, B bị chấm Wrong Answer [2]. Chuỗi đúng định dạng nhưng đoán sai được xử lý theo phần chấm điểm.

Có thể khai báo hàm phụ và biến toàn cục. Hãy đặt các hàm nội bộ và biến toàn cục trong namespace không tên để tránh xung đột với các tệp khác. Hai tiến trình Azzurro và Bordeaux không chia sẻ biến toàn cục.

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

Khi nộp lên LQDOJ, dùng một tệp có #include "casino.h" và hiện thực cả hai hàm. Để chạy thử, biên dịch casino.cpp với trình mẫu grader.cpp bằng:

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

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

Gói gốc chính thức dùng hai tệp Azzurro.cpp, Bordeaux.cpp, lần lượt include Azzurro.h, Bordeaux.h, và biên dịch bằng g++ -std=gnu++20 -O2 -o grader grader.cpp Azzurro.cpp Bordeaux.cpp. Đây là bố cục của gói gốc, không phải yêu cầu nộp hai tệp trên LQDOJ.

Trình mẫu chạy trong một tiến trình, khác với hai tiến trình cô lập khi chấm thật. Trình mẫu đọc stdin theo dạng:

Q N
L_1
S_1
R_1
L_2
S_2
R_2
...
L_Q
S_Q
R_Q

\(R_i\) có độ dài \(2(N-1)\), gồm đúng \(N-1\) ký tự D và \(N-1\) ký tự R. Bắt đầu từ \((0,0)\), đọc lần lượt các ký tự: D là đi xuống một ô, R là đi sang phải một ô. Chuỗi mô tả đường đi của Chiaro.

Trình mẫu in kết quả dạng Accepted: 26, trong đó số là ngưỡng độ dài \(L^*\) được định nghĩa ở phần chấm điểm, hoặc dạng Wrong Answer [1] với mã lỗi tương ứng. Nếu nhiều điều kiện chấm sai cùng xảy ra, chỉ một điều kiện được báo; trình mẫu có thể kết thúc ngay khi phát hiện điều kiện đó.

Dữ liệu vào

Bài nộp nhận dữ liệu qua các đối số của Azzurro và Bordeaux, không đọc stdin. Định dạng dữ liệu để chạy thử với trình mẫu được mô tả ở trên.

Dữ liệu ra

Submission không có standard output; kết quả được trả qua hai hàm chiến lược.

Ràng buộc

• \(N=8\).
• \(1\le Q\le30000\).
• \(1\le L\le51\).
• Chuỗi \(S_i\) có đúng \(L_i\) ký tự, chỉ gồm A và B.
• \(Q,L_i\) là các số nguyên.
• Chuỗi đường đi \(R_i\) có đúng \(N-1\) ký tự D và \(N-1\) ký tự R.
• Mỗi hàm được gọi đúng \(Q\) lần. Đường đi của mỗi lượt được cố định trước khi gọi Azzurro và Bordeaux; grader không thích nghi theo kết quả trả về.

Phân nhóm

Nếu một testcase có ma trận hoặc chuỗi trả về không hợp lệ, lỗi thực thi, quá thời gian, hoặc quá bộ nhớ thì nhận \(0\) điểm. Ngược lại, với mỗi testcase đặt \(L\) là độ dài lớn nhất sao cho mọi lượt có \(L_i\le L\) đều được giải đúng; nếu giải đúng mọi lượt của testcase thì đặt ngưỡng này bằng \(51\). Lấy \(L^*\) là giá trị nhỏ nhất trong các ngưỡng của mọi testcase. Điểm được tính như sau:

• \(1\le L^*\le28\): \(2L^*\) điểm.
• \(29\le L^*\le39\): \(L^*+28\) điểm.
• \(40\le L^*\le50\): \(67+3(L^*-40)\) điểm.
• \(L^*=51\): \(100\) điểm.

Ví dụ giao tiếp

Grader mẫu dùng \(N=2\) chỉ để minh họa giao tiếp (dữ liệu chấm chính thức có \(N=8\)):

Dữ liệu vào đầy đủ của trình mẫu là:

2 2
1
B
RD
3
ABB
DR

Ở lượt đầu, Chiaro đảo màu đường \((0,0)\to(0,1)\to(1,1)\); ở lượt hai, Chiaro đảo màu đường \((0,0)\to(1,0)\to(1,1)\). Bordeaux khôi phục đúng chuỗi trong cả hai lượt.

Ở lượt đầu, Azzurro tô các ô \((0,1),(1,0)\) xanh, các ô \((0,0),(1,1)\) đỏ. Sau khi Chiaro đảo màu, ba ô trên đường đi \((0,0),(0,1),(1,1)\) lần lượt có màu xanh, đỏ, xanh. Bordeaux ghi B và thắng.

Ở lượt hai, Azzurro tô mọi ô xanh. Sau khi Chiaro đảo màu, ba ô trên đường đi \((0,0),(1,0),(1,1)\) đều đỏ. Bordeaux ghi ABB và thắng.

sample-01-in.txt trong gói tương ứng với ví dụ này và không thỏa ràng buộc chính thức. sample-02-in.txt là dữ liệu mẫu thỏa ràng buộc chính thức.

Nguồn

JOI 2025/2026 Final Stage, Cuộc thi 2, bài Casino, Japanese Committee for IOI. Bản dịch được đối chiếu với đề gốc tiếng Nhật và bản tiếng Anh. Đề gốc, bản dịch và bản điều chỉnh được cung cấp theo CC BY-SA 4.0.

Đất nước JOI có \(N\) thị trấn, được đánh số từ \(1\) đến \(N\), và \(N-1\) con đường, được đánh số từ \(1\) đến \(N-1\). Con đường \(j\) (\(1 \le j \le N-1\)) nối hai thị trấn \(U_j\) và \(V_j\) theo cả hai chiều. Có thể đi từ bất kỳ thị trấn nào đến bất kỳ thị trấn nào khác bằng các con đường.

Mỗi thị trấn có một cửa hàng. Cửa hàng ở thị trấn \(i\) (\(1 \le i \le N\)) bán một món quà lưu niệm với giá \(A_i\).

Có \(M\) chuyến du lịch. Chuyến \(k\) đi theo đường đơn duy nhất từ \(S_k\) đến \(T_k\), không lặp thị trấn. Với mỗi ngân sách ứng viên \(B_q\), hãy đếm số bộ \((k,u,v)\) sao cho \(u<v\), chuyến \(k\) đi qua cả \(u,v\), và \(A_u+A_v=B_q\).

Mỗi chuyến đi qua cả thị trấn xuất phát và thị trấn kết thúc. Bạn chọn một chuyến và mua đúng một món quà ở mỗi trong đúng hai thị trấn khác nhau mà chuyến đi qua, sao cho dùng hết ngân sách. Các chỉ số phải thỏa \(1 \le k \le M\) và \(1 \le u<v \le N\).

Dữ liệu vào

• Dòng đầu chứa số nguyên \(N\).
• Dòng thứ hai chứa \(N\) số nguyên \(A_1,\ldots,A_N\).
• \(N-1\) dòng tiếp theo, dòng thứ \(j\) chứa hai số nguyên \(U_j,V_j\).
• Dòng tiếp theo chứa số nguyên \(M\).
• \(M\) dòng tiếp theo, dòng thứ \(k\) chứa hai số nguyên \(S_k,T_k\).
• Dòng tiếp theo chứa số nguyên \(Q\).
• Dòng cuối chứa \(Q\) số nguyên \(B_1,\ldots,B_Q\).

Dữ liệu ra

In \(Q\) dòng; dòng \(q\) là số bộ thỏa ngân sách \(B_q\).

Ràng buộc

• \(2\le N\le100000\), \(1\le A_i\le N\).
• \(1\le U_j,V_j\le N\); \(N-1\) con đường tạo thành một đồ thị liên thông.
• \(1\le M\le200000\); \(1\le S_k,T_k\le N\) và \(S_k\ne T_k\).
• \(1\le Q\le2000\).
• \(1\le B_1<\cdots<B_Q\le2N\).

Mọi giá trị trong dữ liệu vào đều là số nguyên.

Phân nhóm

1. \(3\) điểm: \(N,M,Q\le100\).
2. \(4\) điểm: \(N\le5000\), \(U_j=j\), \(V_j=j+1\) với mọi \(1 \le j \le N-1\).
3. \(5\) điểm: \(N\le5000\).
4. \(6\) điểm: \(Q=1\), \(U_j=j\), \(V_j=j+1\) với mọi \(1 \le j \le N-1\).
5. \(10\) điểm: \(Q=1\).
6. \(7\) điểm: \(M\le1000\), \(U_j=j\), \(V_j=j+1\) với mọi \(1 \le j \le N-1\).
7. \(12\) điểm: \(M\le1000\).
8. \(10\) điểm: \(N,M\le50000\), \(U_j=j\), \(V_j=j+1\) với mọi \(1 \le j \le N-1\).
9. \(15\) điểm: \(N,M\le50000\).
10. \(11\) điểm: \(U_j=j\), \(V_j=j+1\) với mọi \(1 \le j \le N-1\).
11. \(17\) điểm: không có ràng buộc thêm.

Ví dụ

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

0
0
4
2
4
1
0

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

1
2
3
3
1

Nguồn

JOI 2025/2026 Final Stage, Cuộc thi 2, bài JOI Tour 2, Japanese Committee for IOI. Bản dịch được đối chiếu với đề gốc tiếng Nhật và bản tiếng Anh. Đề gốc, bản dịch và bản điều chỉnh được cung cấp theo CC BY-SA 4.0.

Có \(N\) điểm trên một con đường thẳng, được đánh số \(1,2,\ldots,N\) từ trái sang phải. Con đường chỉ cho phép đi một chiều từ trái sang phải. Ngoài ra, có \(M\) máy dịch chuyển được đánh số từ \(1\) đến \(M\); máy \(i\) (\(1 \le i \le M\)) đưa người sử dụng từ điểm \(S_i\) đến điểm \(T_i\), với \(S_i<T_i\).

Bitaro hiện ở điểm \(1\) và muốn đến điểm \(N\). Khi ở điểm \(j\) (\(1 \le j \le N-1\)), cậu có thể đi bộ đến điểm \(j+1\), hoặc chọn một máy \(i\) thỏa \(S_i=j\) để dịch chuyển đến điểm \(T_i\).

Việc dịch chuyển gây áp lực lên cơ thể. Lo lắng cho sự an toàn của Bitaro, bạn quyết định lựa chọn những máy dịch chuyển cần phá hủy (có thể không chọn máy nào) sao cho bất kể cậu chọn đường đi nào, số lần dịch chuyển đều không quá \(K\). Phá hủy máy \(i\) tốn chi phí \(C_i\); sau khi bị phá hủy, máy đó không còn sử dụng được.

Hãy tìm tổng chi phí nhỏ nhất để phá hủy các máy và bảo đảm yêu cầu trên mọi đường đi của Bitaro.

Dữ liệu vào

Dòng đầu gồm \(N,M,K\). \(M\) dòng tiếp theo, dòng \(i\) gồm \(S_i,T_i,C_i\).

Dữ liệu ra

In chi phí nhỏ nhất cần trả.

Ràng buộc

• \(2\le N\le100000\).
• \(1\le K\le M\le100000\).
• \(1\le S_i<T_i\le N\).
• \(1\le C_i\le10^9\).

Mọi giá trị trong dữ liệu vào đều là số nguyên.

Phân nhóm

1. \(5\) điểm: \(K=1\).
2. \(3\) điểm: \(N,M\le20\).
3. \(29\) điểm: \(N,M\le500\).
4. \(23\) điểm: \(N,M\le4000\).
5. \(24\) điểm: \(N,M\le40000\).
6. \(16\) điểm: không có ràng buộc thêm.

Ví dụ

8 4 1
1 4 3
2 3 5
3 6 2
5 8 2

4

12 7 2
1 5 3
4 8 2
2 4 5
2 4 8
7 9 4
9 11 7
3 10 5

6

6 3 2
1 4 2
2 5 4
3 6 3

0

Nguồn

JOI 2025/2026 Final Stage, Cuộc thi 2, bài Teleporter 2, Japanese Committee for IOI. Bản dịch được đối chiếu với đề gốc tiếng Nhật và bản tiếng Anh. Đề gốc, bản dịch và bản điều chỉnh được cung cấp theo CC BY-SA 4.0.