JOI 2024 - Tuyển chọn mùa xuân - Ngày 2

Có một trò chơi trên bàn dành cho \(K\) người chơi. Bàn chơi gồm \(N\) ô được đánh số từ \(1\) đến \(N\) và \(M\) đường đi được đánh số từ \(1\) đến \(M\). Đường đi \(j\) \((1 \le j \le M)\) nối hai ô \(U_j\) và \(V_j\) theo cả hai chiều.

Mỗi ô thuộc một trong hai loại: ô đi tiếp hoặc ô dừng. Thông tin này được mô tả bởi xâu \(S\) có độ dài \(N\), chỉ gồm các ký tự 0 và 1: ký tự thứ \(i\) là 0 nếu ô \(i\) là ô đi tiếp, và là 1 nếu ô \(i\) là ô dừng.

\(K\) người chơi được đánh số từ \(1\) đến \(K\). Mỗi người có một quân cờ của riêng mình. Ban đầu, người chơi \(p\) đặt quân cờ ở ô \(X_p\) \((1 \le p \le K)\). Nhiều quân cờ có thể cùng nằm trên một ô.

Các người chơi lần lượt thực hiện lượt của mình, bắt đầu từ người chơi \(1\) và theo thứ tự tăng dần. Sau lượt của người chơi \(p\) là lượt của người chơi \(p+1\); sau người chơi \(K\) lại đến người chơi \(1\). Trong lượt của mình, một người chơi thực hiện các thao tác sau:

1. Chọn một ô được nối trực tiếp bằng một đường đi với ô đang chứa quân cờ của mình, rồi di chuyển quân cờ đến ô đã chọn.
2. Nếu ô vừa đến là ô đi tiếp, quay lại bước \(1\) và tiếp tục lượt của mình. Nếu đó là ô dừng, kết thúc lượt.

Đội tuyển Nhật Bản gồm \(K\) thành viên, trong đó có JOI-kun, đang nghiên cứu cách phối hợp để hoàn thành trò chơi thật nhanh. Họ quan tâm đến câu hỏi: tổng số lần di chuyển ít nhất của cả \(K\) người chơi để đưa quân cờ của người chơi \(1\) đến ô \(T\) là bao nhiêu? Điều kiện được coi là thỏa mãn ngay khi quân cờ của người chơi \(1\) đến ô \(T\), kể cả khi lượt hiện tại chưa kết thúc.

Cho thông tin về bàn chơi và vị trí ban đầu của các quân cờ, hãy tính câu trả lời cho từng \(T=1,2,\ldots,N\).

Dữ liệu vào

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

N M K
U_1 V_1
U_2 V_2
...
U_M V_M
S
X_1 X_2 ... X_K

Dữ liệu ra

In \(N\) dòng ra đầu ra chuẩn. Dòng thứ \(T\) \((1 \le T \le N)\) chứa tổng số lần di chuyển ít nhất của cả \(K\) người chơi để đưa quân cờ của người chơi \(1\) đến ô \(T\).

Ràng buộc

• \(2 \le N \le 50\,000\).
• \(1 \le M \le 50\,000\).
• \(2 \le K \le 50\,000\).
• \(1 \le U_j < V_j \le N\) \((1 \le j \le M)\).
• \((U_j,V_j) \ne (U_k,V_k)\) với mọi \(1 \le j < k \le M\).
• Từ một ô bất kỳ có thể đi đến mọi ô khác bằng cách đi qua một số đường đi.
• \(S\) có độ dài \(N\) và chỉ gồm các ký tự 0, 1.
• \(1 \le X_p \le N\) \((1 \le p \le K)\).
• \(N,M,K,U_j,V_j,X_p\) đều là số nguyên.

Phân nhóm

• Nhóm 1 (3 điểm): Không có ô dừng.
• Nhóm 2 (7 điểm): Có đúng một ô dừng.
• Nhóm 3 (7 điểm): Có đúng hai ô dừng.
• Nhóm 4 (19 điểm): \(N \le 3\,000\), \(M \le 3\,000\), \(K \le 3\,000\).
• Nhóm 5 (23 điểm): \(K=2\).
• Nhóm 6 (9 điểm): \(K \le 100\).
• Nhóm 7 (23 điểm): \(N \le 30\,000\), \(M \le 30\,000\), \(K \le 30\,000\).
• Nhóm 8 (9 điểm): Không có ràng buộc bổ sung.

Ví dụ

5 5 2
1 2
2 3
2 4
3 5
4 5
00000
1 5

0
1
2
2
3

5 5 2
1 2
2 3
2 4
3 5
4 5
01000
1 5

0
1
4
4
5

5 5 2
1 2
2 3
2 4
3 5
4 5
01100
1 5

0
1
3
3
4

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

4
2
3
0
10
1
17
24

12 13 3
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 9
9 10
1 10
2 9
7 12
11 12
110000011101
1 9 11

0
1
4
5
6
7
8
8
4
1
13
9

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.

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.

Bitaro đã yêu thích việc làm vườn từ nhiều năm nay. Bắt đầu từ mùa xuân này, cậu dự định trồng một loại cây tên là củ cải Bita.

Bitaro đã chuẩn bị \(2N\) cây giống củ cải Bita, được đánh số từ \(1\) đến \(2N\), và sẽ xếp chúng theo đúng thứ tự đó để trồng. Kích thước của cây giống \(i\) \((1 \le i \le 2N)\) là \(A_i\). Để mọi cây đều nhận đủ ánh sáng, kích thước của chúng thỏa mãn:

• \(A_1 \le A_2 \le \cdots \le A_N \le A_{N+1}\).
• \(A_{N+1} \ge A_{N+2} \ge \cdots \ge A_{2N-1} \ge A_{2N} \ge A_1\).

Như vậy, cây giống \(1\) có kích thước nhỏ nhất và cây giống \(N+1\) có kích thước lớn nhất.

Bitaro cũng đã chuẩn bị \(N\) chậu màu đỏ và \(N\) chậu màu xanh lam. Chậu đỏ thứ \(j\) \((1 \le j \le N)\) có kích thước \(B_j\); chậu xanh lam thứ \(k\) \((1 \le k \le N)\) có kích thước \(C_k\). Cậu trồng một cây giống vào mỗi chậu trong số \(2N\) chậu này, rồi xếp các chậu thành một hàng sao cho các cây giống xuất hiện theo thứ tự \(1,2,\ldots,2N\).

Để đẹp mắt, các chậu phải được xếp theo một thứ tự đẹp: tồn tại \(N\) chậu liên tiếp cùng màu. Chính xác hơn, thứ tự được gọi là đẹp khi và chỉ khi tồn tại số nguyên \(l\), \(1 \le l \le N+1\), sao cho các chậu chứa cây giống \(l,l+1,\ldots,l+N-1\) đều có cùng màu.

Khi trồng cây giống có kích thước \(y\) vào chậu có kích thước \(x\), độ khó chăm sóc của cặp đó là \(|x-y|\). Khối lượng công việc của Bitaro là độ khó chăm sóc lớn nhất trong \(2N\) cặp chậu và cây giống.

Cho thông tin về các cây giống và các chậu, hãy tìm khối lượng công việc nhỏ nhất có thể khi trồng cây sao cho thứ tự các chậu là đẹp.

Dữ liệu vào

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

N
A_1 A_2 ... A_{2N}
B_1 B_2 ... B_N
C_1 C_2 ... C_N

Dữ liệu ra

In một số trên một dòng ra đầu ra chuẩn: khối lượng công việc nhỏ nhất có thể của Bitaro khi trồng cây sao cho thứ tự các chậu là đẹp.

Ràng buộc

• \(1 \le N \le 300\,000\).
• \(1 \le A_i \le 10^9\) \((1 \le i \le 2N)\).
• \(1 \le B_j \le 10^9\) \((1 \le j \le N)\).
• \(1 \le C_k \le 10^9\) \((1 \le k \le N)\).
• \(A_1 \le A_2 \le \cdots \le A_N \le A_{N+1}\).
• \(A_{N+1} \ge A_{N+2} \ge \cdots \ge A_{2N-1} \ge A_{2N} \ge A_1\).
• Mọi giá trị đầu vào đều là số nguyên.

Phân nhóm

• Nhóm 1 (4 điểm): \(N \le 5\).
• Nhóm 2 (5 điểm): \(N \le 10\).
• Nhóm 3 (21 điểm): \(N \le 2\,000\).
• Nhóm 4 (37 điểm): Các giá trị \(A_i\) đôi một khác nhau và \(A_N < A_{2N}\).
• Nhóm 5 (33 điểm): Không có ràng buộc bổ sung.

Ví dụ

2
1 2 6 3
2 5
4 3

2

9
1 2 3 4 5 6 7 8 9 18 17 16 15 14 13 12 11 10
2 7 4 1 7 6 4 10 6
6 8 9 3 7 1 9 5 4

8

7
13 16 18 18 21 22 22 23 23 21 19 17 15 14
14 14 20 19 22 17 25
24 15 18 25 24 19 11

3

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.