IOI 2023 - Ngày 2

Vétyem Woods là một khu rừng nổi tiếng với nhiều cây cối đủ sắc màu. Một trong những cây dẻ gai cổ nhất và cao nhất có tên là Ős Vezér.

Cây Ős Vezér được mô hình hóa bằng \(N\) đỉnh và \(N-1\) cạnh. Các đỉnh được đánh số từ \(0\) đến \(N-1\), các cạnh từ \(1\) đến \(N-1\). Mỗi cạnh nối hai đỉnh khác nhau. Cụ thể, cạnh \(i\) (\(1\le i<N\)) nối đỉnh \(i\) với đỉnh \(P[i]\), trong đó \(0\le P[i]<i\). Đỉnh \(P[i]\) được gọi là cha của đỉnh \(i\), và đỉnh \(i\) là con của đỉnh \(P[i]\).

Mỗi cạnh có một màu. Có \(M\) màu có thể có, đánh số từ \(1\) đến \(M\). Màu của cạnh \(i\) là \(C[i]\). Các cạnh khác nhau có thể cùng màu.

Trong định nghĩa trên, \(i=0\) không tương ứng với cạnh nào. Để thuận tiện, đặt \(P[0]=-1\) và \(C[0]=0\).

Ví dụ, giả sử cây có \(N=18\) đỉnh và \(M=3\) màu, với \(17\) cạnh được mô tả bởi:

Cây được mô tả trong hình sau:

Árpád là một người kiểm lâm tài năng, thích nghiên cứu những phần của cây gọi là cây con. Với mỗi \(r\) thỏa mãn \(0\le r<N\), cây con của đỉnh \(r\) là tập \(T(r)\) các đỉnh có những tính chất sau:

• Đỉnh \(r\) thuộc \(T(r)\).
• Khi một đỉnh \(x\) thuộc \(T(r)\) thì mọi đỉnh con của \(x\) cũng thuộc \(T(r)\).
• Không có đỉnh nào khác thuộc \(T(r)\).

Kích thước của tập \(T(r)\) được ký hiệu là \(|T(r)|\).

Gần đây, Árpád phát hiện một tính chất phức tạp nhưng thú vị của cây con. Phát hiện này cần rất nhiều thử nghiệm bằng giấy bút, và anh ấy nghĩ bạn cũng có thể cần làm như vậy để hiểu tính chất đó. Anh ấy sẽ đưa ra nhiều ví dụ để bạn phân tích chi tiết.

Giả sử cố định \(r\) và một hoán vị \(v_0,v_1,\ldots,v_{|T(r)|-1}\) của các đỉnh trong \(T(r)\). Với mỗi \(i\) thỏa mãn \(1\le i<|T(r)|\), gọi \(f(i)\) là số lần màu \(C[v_i]\) xuất hiện trong dãy \(i-1\) màu \(C[v_1],C[v_2],\ldots,C[v_{i-1}]\).

Lưu ý rằng \(f(1)\) luôn bằng \(0\) vì dãy màu trong định nghĩa là rỗng.

Hoán vị \(v_0,v_1,\ldots,v_{|T(r)|-1}\) là hoán vị đẹp khi và chỉ khi thỏa mãn tất cả các tính chất sau:

• \(v_0=r\).
• Với mỗi \(i\) thỏa mãn \(1\le i<|T(r)|\), cha của đỉnh \(v_i\) là đỉnh \(v_{f(i)}\).

Với mỗi \(r\) thỏa mãn \(0\le r<N\), cây con \(T(r)\) là cây con đẹp khi và chỉ khi tồn tại một hoán vị đẹp của các đỉnh trong \(T(r)\). Theo định nghĩa này, mọi cây con chỉ có một đỉnh đều đẹp.

Xét cây ví dụ ở trên. Có thể chứng minh \(T(0)\) và \(T(3)\) không đẹp. Cây con \(T(14)\) đẹp vì chỉ có một đỉnh. Dưới đây, ta sẽ chứng minh \(T(1)\) cũng đẹp.

Xét dãy số nguyên khác nhau \([v_0,v_1,v_2,v_3,v_4,v_5,v_6]=[1,4,5,12,13,6,14]\). Đây là một hoán vị của các đỉnh trong \(T(1)\). Hình sau mô tả hoán vị này; nhãn gắn với mỗi đỉnh là chỉ số mà đỉnh đó xuất hiện trong hoán vị.

Ta kiểm tra đây là một hoán vị đẹp:

• \(v_0=1\).
• \(f(1)=0\) vì \(C[v_1]=C[4]=1\) xuất hiện \(0\) lần trong dãy \([]\). Tương ứng, cha của \(v_1\) là \(v_0\): cha của đỉnh \(4\) là đỉnh \(1\), tức \(P[4]=1\).
• \(f(2)=0\) vì \(C[v_2]=C[5]=2\) xuất hiện \(0\) lần trong dãy \([1]\). Tương ứng, cha của \(v_2\) là \(v_0\): cha của đỉnh \(5\) là đỉnh \(1\).
• \(f(3)=1\) vì \(C[v_3]=C[12]=1\) xuất hiện \(1\) lần trong dãy \([1,2]\). Tương ứng, cha của \(v_3\) là \(v_1\): cha của đỉnh \(12\) là đỉnh \(4\).
• \(f(4)=1\) vì \(C[v_4]=C[13]=2\) xuất hiện \(1\) lần trong dãy \([1,2,1]\). Tương ứng, cha của \(v_4\) là \(v_1\): cha của đỉnh \(13\) là đỉnh \(4\).
• \(f(5)=0\) vì \(C[v_5]=C[6]=3\) xuất hiện \(0\) lần trong dãy \([1,2,1,2]\). Tương ứng, cha của \(v_5\) là \(v_0\): cha của đỉnh \(6\) là đỉnh \(1\).
• \(f(6)=2\) vì \(C[v_6]=C[14]=2\) xuất hiện \(2\) lần trong dãy \([1,2,1,2,3]\). Tương ứng, cha của \(v_6\) là \(v_2\): cha của đỉnh \(14\) là đỉnh \(5\).

Vì tìm được một hoán vị đẹp của các đỉnh trong \(T(1)\), cây con \(T(1)\) là cây con đẹp.

Nhiệm vụ của bạn là giúp Árpád xác định với mỗi cây con của cây Ős Vezér, cây con đó có đẹp hay không.

Chi tiết cài đặt

Bạn cần cài đặt hàm sau:

std::vector<int> beechtree(
    int N, int M, std::vector<int> P, std::vector<int> C);

• \(N\): số đỉnh của cây.
• \(M\): số màu có thể có của các cạnh.
• \(P,C\): các mảng độ dài \(N\) mô tả các cạnh của cây.
• Hàm cần trả về mảng \(b\) có độ dài \(N\). Với mỗi \(r\) thỏa mãn \(0\le r<N\), \(b[r]=1\) nếu \(T(r)\) đẹp, và \(b[r]=0\) nếu ngược lại.
• Hàm được gọi đúng một lần cho mỗi test.

Các ví dụ

Ví dụ 1

Xét lời gọi sau:

beechtree(4, 2, [-1, 0, 0, 0], [0, 1, 1, 2])

Cây tương ứng được mô tả trong hình sau:

\(T(1)\), \(T(2)\) và \(T(3)\) mỗi cây chỉ có một đỉnh nên đều đẹp. \(T(0)\) không đẹp. Vì vậy, hàm cần trả về \([0,1,1,1]\).

Ví dụ 2

Xét lời gọi sau:

beechtree(18, 3,
          [-1, 0, 0, 0, 1, 1, 1, 2, 2, 3, 3, 3, 4, 4, 5, 10, 11, 11],
          [0, 1, 2, 3, 1, 2, 3, 1, 3, 3, 2, 1, 1, 2, 2, 1, 2, 3])

Ví dụ này được minh họa trong phần mô tả bài toán ở trên. Hàm cần trả về \([0,1,1,0,1,1,1,1,1,1,1,1,1,1,1,1,1,1]\).

Ví dụ 3

Xét lời gọi sau:

beechtree(7, 2, [-1, 0, 1, 1, 0, 4, 5], [0, 1, 1, 2, 2, 1, 1])

Ví dụ này được minh họa trong hình sau:

\(T(0)\) là cây con duy nhất không đẹp. Hàm cần trả về \([0,1,1,1,1,1,1]\).

Các ràng buộc

• \(3\le N\le 200\,000\).
• \(2\le M\le 200\,000\).
• \(0\le P[i]<i\) với mỗi \(i\) thỏa mãn \(1\le i<N\).
• \(1\le C[i]\le M\) với mỗi \(i\) thỏa mãn \(1\le i<N\).
• \(P[0]=-1\) và \(C[0]=0\).

Các subtask

Subtask	Điểm	Ràng buộc bổ sung
1	9	\(N\le 8\) và \(M\le 500\).
2	5	Cạnh \(i\) nối đỉnh \(i\) với đỉnh \(i-1\), tức \(P[i]=i-1\) với mỗi \(1\le i<N\).
3	9	Mỗi đỉnh khác \(0\) nối với đỉnh \(0\) hoặc với một đỉnh nối với \(0\). Tức là, với mỗi \(1\le i<N\), \(P[i]=0\) hoặc \(P[P[i]]=0\).
4	8	Với mỗi \(1\le c\le M\), có nhiều nhất hai cạnh màu \(c\).
5	14	\(N\le 200\) và \(M\le 500\).
6	14	\(N\le 2\,000\) và \(M=2\).
7	12	\(N\le 2\,000\).
8	17	\(M=2\).
9	12	Không có ràng buộc nào thêm.

Trình chấm mẫu

Trình chấm mẫu đọc dữ liệu vào theo định dạng sau:

dòng 1: N M
dòng 2: P[0] P[1] … P[N − 1]
dòng 3: C[0] C[1] … C[N − 1]

Gọi \(b[0],b[1],\ldots\) là các phần tử của mảng do beechtree trả về. Trình chấm mẫu in câu trả lời trên một dòng theo định dạng sau:

dòng 1: b[0] b[1] …

---

Nguồn: Olympic Tin học Quốc tế 2023 (IOI 2023). Bản dịch tiếng Việt chính thức của đoàn Việt Nam, được đối chiếu với đề tiếng Anh chính thức. Nội dung đề được phát hành theo giấy phép CC BY.

Có một con đường một làn, một chiều từ sân bay Budapest đến khách sạn Forrás. Con đường dài \(L\) kilômét.

Trong sự kiện IOI 2023, \(N+1\) xe buýt đi qua con đường này, được đánh số từ \(0\) đến \(N\). Xe buýt \(i\) (\(0\le i<N\)) dự kiến rời sân bay vào giây thứ \(T[i]\) của sự kiện và có thể đi \(1\) kilômét trong \(W[i]\) giây. Xe buýt \(N\) là xe dự phòng, có thể đi \(1\) kilômét trong \(X\) giây. Thời điểm \(Y\) mà xe dự phòng rời sân bay chưa được xác định.

Thông thường không được phép vượt trên đường, nhưng các xe buýt được vượt nhau tại trạm phân loại. Có \(M\) trạm phân loại (\(M>1\)), đánh số từ \(0\) đến \(M-1\), ở những vị trí khác nhau trên đường. Trạm \(j\) (\(0\le j<M\)) cách sân bay \(S[j]\) kilômét dọc theo đường. Các trạm được sắp xếp theo khoảng cách tăng dần từ sân bay, tức \(S[j]<S[j+1]\) với mỗi \(0\le j\le M-2\). Trạm đầu tiên là sân bay, trạm cuối là khách sạn: \(S[0]=0\) và \(S[M-1]=L\).

Mỗi xe buýt đi với tốc độ tối đa, trừ khi đuổi kịp một xe chậm hơn phía trước. Khi đó, chúng bị dồn lại và phải đi với tốc độ của xe chậm hơn cho đến trạm phân loại tiếp theo. Tại đó, các xe nhanh hơn sẽ vượt các xe chậm hơn.

Cụ thể, với mỗi \(0\le i\le N\) và \(0\le j<M\), thời điểm \(t_{i,j}\) (tính bằng giây) mà xe buýt \(i\) đến trạm \(j\) được xác định như sau. Đặt \(t_{i,0}=T[i]\) với mỗi \(0\le i<N\), và \(t_{N,0}=Y\). Với mỗi \(j\) thỏa mãn \(0<j<M\):

• Thời điểm dự kiến đến trạm \(j\) của xe \(i\), ký hiệu \(e_{i,j}\), là thời điểm xe đến trạm \(j\) nếu đi với tốc độ tối đa kể từ khi đến trạm \(j-1\). Tức là:

• Xe \(i\) đến trạm \(j\) tại thời điểm lớn nhất trong các thời điểm dự kiến đến của chính nó và của mọi xe khác đã đến trạm \(j-1\) sớm hơn nó. Cụ thể, \(t_{i,j}\) là giá trị lớn nhất của \(e_{i,j}\) và mọi \(e_{k,j}\) thỏa mãn \(0\le k\le N\) và \(t_{k,j-1}<t_{i,j-1}\).

Ban tổ chức IOI muốn lên lịch cho xe dự phòng (xe \(N\)). Nhiệm vụ của bạn là trả lời \(Q\) câu hỏi: cho thời điểm \(Y\) (tính bằng giây) xe dự phòng rời sân bay, xe sẽ đến khách sạn vào thời điểm nào?

Chi tiết cài đặt

Bạn cần cài đặt các hàm sau:

void init(int L, int N, std::vector<long long> T, std::vector<int> W,
          int X, int M, std::vector<int> S);

• \(L\): chiều dài con đường.
• \(N\): số xe buýt không phải xe dự phòng.
• \(T\): mảng độ dài \(N\) mô tả thời điểm khởi hành dự kiến từ sân bay của các xe không phải xe dự phòng.
• \(W\): mảng độ dài \(N\) mô tả tốc độ tối đa của các xe không phải xe dự phòng.
• \(X\): thời gian để xe dự phòng đi \(1\) kilômét.
• \(M\): số trạm phân loại.
• \(S\): mảng độ dài \(M\) mô tả khoảng cách từ sân bay đến các trạm phân loại.
• Hàm được gọi đúng một lần cho mỗi test, trước mọi lời gọi arrival_time.

long long arrival_time(long long Y);

• \(Y\): thời điểm xe dự phòng (xe \(N\)) dự kiến rời sân bay.
• Hàm cần trả về thời điểm xe dự phòng đến khách sạn.
• Hàm được gọi đúng \(Q\) lần.

Ví dụ

Xét dãy lời gọi sau:

init(6, 4, [20, 10, 40, 0], [5, 20, 20, 30], 10, 4, [0, 1, 3, 6])

Bỏ qua xe \(4\) chưa được lên lịch, bảng sau cho biết thời điểm đến dự kiến và thực tế của các xe không phải xe dự phòng tại mỗi trạm:

\(i\)	\(t_{i,0}\)	\(e_{i,1}\)	\(t_{i,1}\)	\(e_{i,2}\)	\(t_{i,2}\)	\(e_{i,3}\)	\(t_{i,3}\)
0	20	25	30	40	40	55	55
1	10	30	30	70	70	130	130
2	40	60	60	100	100	160	180
3	0	30	30	90	90	180	180

Thời điểm đến trạm \(0\) là thời điểm dự kiến rời sân bay: \(t_{i,0}=T[i]\) với \(0\le i\le 3\).

Các thời điểm dự kiến đến trạm \(1\) được tính như sau:

• Xe \(0\): \(e_{0,1}=t_{0,0}+W[0]\cdot(S[1]-S[0])=20+5\cdot1=25\).
• Xe \(1\): \(e_{1,1}=t_{1,0}+W[1]\cdot(S[1]-S[0])=10+20\cdot1=30\).
• Xe \(2\): \(e_{2,1}=t_{2,0}+W[2]\cdot(S[1]-S[0])=40+20\cdot1=60\).
• Xe \(3\): \(e_{3,1}=t_{3,0}+W[3]\cdot(S[1]-S[0])=0+30\cdot1=30\).

Các thời điểm thực tế đến trạm \(1\) được tính như sau:

• Xe \(1\) và \(3\) đến trạm \(0\) sớm hơn xe \(0\), nên \(t_{0,1}=\max([e_{0,1},e_{1,1},e_{3,1}])=30\).
• Xe \(3\) đến trạm \(0\) sớm hơn xe \(1\), nên \(t_{1,1}=\max([e_{1,1},e_{3,1}])=30\).
• Xe \(0\), \(1\) và \(3\) đến trạm \(0\) sớm hơn xe \(2\), nên \(t_{2,1}=\max([e_{0,1},e_{1,1},e_{2,1},e_{3,1}])=60\).
• Không xe nào đến trạm \(0\) sớm hơn xe \(3\), nên \(t_{3,1}=\max([e_{3,1}])=30\).

arrival_time(0)

Xe \(4\) mất \(10\) giây để đi \(1\) kilômét và được lên lịch rời sân bay ở giây thứ \(0\). Bảng sau cho biết các thời điểm đến của mỗi xe. Thay đổi duy nhất trong thời điểm đến dự kiến và thực tế của các xe không phải xe dự phòng được gạch chân.

\(i\)	\(t_{i,0}\)	\(e_{i,1}\)	\(t_{i,1}\)	\(e_{i,2}\)	\(t_{i,2}\)	\(e_{i,3}\)	\(t_{i,3}\)
0	20	25	30	40	40	55	<u>60</u>
1	10	30	30	70	70	130	130
2	40	60	60	100	100	160	180
3	0	30	30	90	90	180	180
4	0	10	10	30	30	60	60

Xe \(4\) đến khách sạn ở giây thứ \(60\). Vì vậy, hàm cần trả về \(60\).

arrival_time(50)

Xe \(4\) được lên lịch rời sân bay ở giây thứ \(50\). Các thời điểm đến của các xe không phải xe dự phòng không thay đổi so với bảng ban đầu. Các thời điểm đến được thể hiện trong bảng sau:

\(i\)	\(t_{i,0}\)	\(e_{i,1}\)	\(t_{i,1}\)	\(e_{i,2}\)	\(t_{i,2}\)	\(e_{i,3}\)	\(t_{i,3}\)
0	20	25	30	40	40	55	55
1	10	30	30	70	70	130	130
2	40	60	60	100	100	160	180
3	0	30	30	90	90	180	180
4	50	60	60	80	90	120	130

Xe \(4\) vượt xe \(2\) chậm hơn tại trạm \(1\) khi chúng đến cùng lúc. Tiếp theo, xe \(4\) bị dồn lại với xe \(3\) giữa trạm \(1\) và trạm \(2\), khiến xe \(4\) đến trạm \(2\) ở giây thứ \(90\) thay vì \(80\). Sau khi rời trạm \(2\), xe \(4\) bị dồn lại với xe \(1\) cho đến khách sạn. Xe \(4\) đến khách sạn ở giây thứ \(130\), nên hàm cần trả về \(130\).

Ta có thể vẽ đồ thị thời điểm mỗi xe đến từng khoảng cách từ sân bay. Trục \(x\) biểu diễn khoảng cách từ sân bay (kilômét), trục \(y\) biểu diễn thời điểm (giây). Các đường nét đứt dọc đánh dấu vị trí trạm phân loại. Các đường liền nét khác nhau, kèm chỉ số xe, biểu diễn bốn xe không phải xe dự phòng. Đường chấm màu đen biểu diễn xe dự phòng.

Đồ thị cho arrival_time(0):

Đồ thị cho arrival_time(50):

Các ràng buộc

• \(1\le L\le 10^9\).
• \(1\le N\le 1\,000\).
• \(0\le T[i]\le 10^{18}\) với mỗi \(0\le i<N\).
• \(1\le W[i]\le 10^9\) với mỗi \(0\le i<N\).
• \(1\le X\le 10^9\).
• \(2\le M\le 1\,000\).
• \(0=S[0]<S[1]<\cdots<S[M-1]=L\).
• \(1\le Q\le 10^6\).
• \(0\le Y\le 10^{18}\).

Các subtask

Subtask	Điểm	Ràng buộc bổ sung
1	9	\(N=1\), \(Q\le 1\,000\).
2	10	\(M=2\), \(Q\le 1\,000\).
3	20	\(N,M,Q\le 100\).
4	26	\(Q\le 5\,000\).
5	35	Không có ràng buộc nào thêm.

Trình chấm mẫu

Trình chấm mẫu đọc dữ liệu vào theo định dạng sau:

dòng 1: L N X M Q
dòng 2: T[0] T[1] … T[N − 1]
dòng 3: W[0] W[1] … W[N − 1]
dòng 4: S[0] S[1] … S[M − 1]
dòng 5 + k (0 ≤ k < Q): Y cho câu hỏi k

Trình chấm mẫu in các câu trả lời theo định dạng sau:

dòng 1 + k (0 ≤ k < Q): giá trị trả về của arrival_time cho câu hỏi k

---

Nguồn: Olympic Tin học Quốc tế 2023 (IOI 2023). Bản dịch tiếng Việt chính thức của đoàn Việt Nam, được đối chiếu với đề tiếng Anh chính thức. Nội dung đề được phát hành theo giấy phép CC BY.

Các nhà nghiên cứu AI tại Đại học Szeged đang tổ chức một cuộc thi lập trình robot. Bạn của bạn, Hanga, quyết định tham gia. Mục tiêu là lập trình Pulibot tối thượng, với sự ngưỡng mộ dành cho trí thông minh tuyệt vời của Puli, giống chó chăn gia súc nổi tiếng của Hungary.

Pulibot được thử nghiệm trên mê cung gồm một lưới \((H+2)\times(W+2)\) ô. Các hàng được đánh số từ \(-1\) đến \(H\) theo hướng bắc–nam, các cột từ \(-1\) đến \(W\) theo hướng tây–đông. Ô ở hàng \(r\), cột \(c\) (\(-1\le r\le H\), \(-1\le c\le W\)) được gọi là ô \((r,c)\).

Với \(0\le r<H\) và \(0\le c<W\), ô \((r,c)\) có \(4\) ô liền kề:

• Ô \((r,c-1)\) ở phía tây.
• Ô \((r+1,c)\) ở phía nam.
• Ô \((r,c+1)\) ở phía đông.
• Ô \((r-1,c)\) ở phía bắc.

Ô \((r,c)\) là ô biên giới của mê cung nếu \(r=-1\), \(r=H\), \(c=-1\) hoặc \(c=W\). Mỗi ô không phải ô biên giới là ô chướng ngại vật hoặc ô trống. Mỗi ô trống có một màu, biểu diễn bằng số nguyên không âm từ \(0\) đến \(Z_{MAX}\), kể cả hai đầu. Ban đầu, mọi ô trống có màu \(0\).

Ví dụ, xét mê cung có \(H=4\), \(W=5\), với một ô chướng ngại vật \((1,3)\):

Ô chướng ngại vật duy nhất được đánh dấu bằng dấu chữ thập. Các ô biên giới được tô đậm. Số trong mỗi ô trống biểu diễn màu của ô đó.

Một đường đi có độ dài \(\ell\) (\(\ell>0\)) từ ô \((r_0,c_0)\) đến ô \((r_\ell,c_\ell)\) là dãy các ô trống đôi một khác nhau \((r_0,c_0),(r_1,c_1),\ldots,(r_\ell,c_\ell)\), trong đó với mỗi \(0\le i<\ell\), các ô \((r_i,c_i)\) và \((r_{i+1},c_{i+1})\) liền kề nhau.

Lưu ý rằng đường đi độ dài \(\ell\) chứa đúng \(\ell+1\) ô.

Các nhà nghiên cứu thiết lập một mê cung có ít nhất một đường đi từ \((0,0)\) đến \((H-1,W-1)\). Điều này đảm bảo hai ô \((0,0)\) và \((H-1,W-1)\) đều trống. Hanga không biết những ô nào trống và những ô nào là chướng ngại vật.

Nhiệm vụ của bạn là giúp Hanga lập trình Pulibot tìm một đường đi ngắn nhất, tức đường đi có độ dài nhỏ nhất, từ \((0,0)\) đến \((H-1,W-1)\) trong mê cung chưa biết trước. Thông số kỹ thuật của Pulibot và quy tắc cuộc thi được mô tả dưới đây.

Phần cuối của đề mô tả một công cụ hiển thị mà bạn có thể dùng để trực quan hóa Pulibot.

Thông số kỹ thuật của Pulibot

Với mỗi \(-1\le r\le H\) và \(-1\le c\le W\), trạng thái của ô \((r,c)\) là số nguyên được xác định như sau:

• Nếu là ô biên giới, trạng thái là \(-2\).
• Nếu là ô chướng ngại vật, trạng thái là \(-1\).
• Nếu là ô trống, trạng thái là màu của ô.

Chương trình của Pulibot thực hiện một dãy các bước. Trong mỗi bước, Pulibot nhận biết trạng thái các ô lân cận rồi thực hiện một lệnh được xác định bởi những trạng thái đó.

Giả sử đầu bước hiện tại, Pulibot ở ô trống \((r,c)\). Bước này được thực hiện như sau:

1. Pulibot nhận dạng mảng trạng thái hiện tại \(S=[S[0],S[1],S[2],S[3],S[4]]\), gồm trạng thái ô \((r,c)\) và mọi ô liền kề. \(S[0]\) là trạng thái ô \((r,c)\); \(S[1]\), \(S[2]\), \(S[3]\), \(S[4]\) lần lượt là trạng thái các ô phía tây, nam, đông, bắc.
2. Pulibot xác định lệnh \((Z,A)\) tương ứng với mảng trạng thái vừa nhận dạng.
3. Pulibot thực hiện lệnh: đặt màu ô \((r,c)\) thành \(Z\), rồi thực hiện hành động \(A\). Hành động này là ở lại ô \((r,c)\), di chuyển đến một trong \(4\) ô liền kề, hoặc kết thúc chương trình.

Ví dụ, xét tình huống bên trái hình sau. Pulibot ở ô \((0,0)\) có màu \(0\) và nhận dạng mảng \(S=[0,-2,2,2,-2]\). Chương trình có thể quy định rằng khi nhận dạng mảng này, Pulibot đặt màu ô hiện tại thành \(Z=1\) rồi di chuyển về phía đông, như ở giữa và bên phải hình:

Các quy tắc Cuộc thi Robot

• Ban đầu, Pulibot được đặt ở ô \((0,0)\) và bắt đầu thực hiện chương trình.
• Pulibot không được di chuyển đến ô không trống.
• Chương trình phải kết thúc sau tối đa \(500\,000\) bước.
• Sau khi chương trình kết thúc, phải tồn tại một đường đi ngắn nhất từ \((0,0)\) đến \((H-1,W-1)\) mà mọi ô trên đường đi có màu \(1\). Tất cả các ô trống khác phải có màu \(0\).
• Pulibot có thể kết thúc chương trình tại bất kỳ ô trống nào.

Ví dụ, hình sau mô tả một mê cung có \(H=W=6\). Cấu hình ban đầu ở bên trái và một cách tô màu hợp lệ sau khi kết thúc ở bên phải:

Chi tiết cài đặt

Bạn cần cài đặt hàm sau:

void program_pulibot();

• Hàm cần tạo chương trình của Pulibot. Chương trình này phải chạy đúng với mọi giá trị \(H\), \(W\) và mọi mê cung thỏa mãn các ràng buộc của bài toán.
• Hàm được gọi đúng một lần cho mỗi test.

Hàm này có thể gọi hàm sau để tạo chương trình của Pulibot:

void set_instruction(std::vector<int> S, int Z, char A);

• \(S\): mảng độ dài \(5\) mô tả một mảng trạng thái.
• \(Z\): số nguyên không âm biểu diễn một màu.
• \(A\): một ký tự biểu diễn hành động theo bảng sau.

Ký tự	Hành động
H	Ở lại.
W	Di chuyển về phía tây.
S	Di chuyển về phía nam.
E	Di chuyển về phía đông.
N	Di chuyển về phía bắc.
T	Kết thúc chương trình.

Lời gọi này hướng dẫn Pulibot thực hiện lệnh \((Z,A)\) khi nhận dạng mảng trạng thái \(S\).

Gọi hàm nhiều lần với cùng một mảng trạng thái \(S\) sẽ nhận phản hồi Output isn't correct.

Không bắt buộc gọi set_instruction cho mọi mảng trạng thái \(S\) có thể có. Tuy nhiên, nếu Pulibot gặp mảng trạng thái chưa được đặt lệnh, bạn sẽ nhận phản hồi Output isn't correct.

Sau khi program_pulibot hoàn thành, trình chấm chạy chương trình của Pulibot trên một hoặc nhiều mê cung. Những lần chạy này không tính vào giới hạn thời gian của lời giải. Trình chấm không thích nghi: tập các mê cung trong mỗi test được xác định trước.

Nếu Pulibot vi phạm bất kỳ quy tắc nào của Cuộc thi Robot trước khi kết thúc chương trình, bạn sẽ nhận phản hồi Output isn't correct.

Ví dụ

Hàm program_pulibot có thể gọi set_instruction như sau:

set_instruction([0, -2, -1, 0, -2], 1, E)
set_instruction([0, 1, -1, 0, -2], 1, E)
set_instruction([0, 1, 0, -2, -2], 1, S)
set_instruction([0, -1, -2, -2, 1], 1, T)

Lời gọi	Lệnh cho mảng trạng thái \(S\)
1	Đặt màu thành \(1\) và di chuyển về phía đông.
2	Đặt màu thành \(1\) và di chuyển về phía đông.
3	Đặt màu thành \(1\) và di chuyển về phía nam.
4	Đặt màu thành \(1\) và kết thúc chương trình.

Xét tình huống \(H=2\), \(W=3\), với mê cung sau:

Với mê cung cụ thể này, chương trình chạy trong bốn bước. Các mảng trạng thái Pulibot nhận dạng và các lệnh nó thực hiện tương ứng chính xác với bốn lời gọi set_instruction ở trên, theo đúng thứ tự. Lệnh cuối kết thúc chương trình.

Hình sau mô tả mê cung trước mỗi bước trong bốn bước và các màu cuối cùng sau khi kết thúc:

Tuy nhiên, chương trình gồm \(4\) lệnh này có thể không tìm được đường đi ngắn nhất trong những mê cung hợp lệ khác. Vì vậy, nếu nộp, chương trình sẽ nhận phản hồi Output isn't correct.

Các ràng buộc

\(Z_{MAX}=19\). Do đó, Pulibot có thể dùng các màu từ \(0\) đến \(19\), kể cả hai đầu.

Với mỗi mê cung dùng để kiểm thử Pulibot:

• \(2\le H,W\le 15\).
• Có ít nhất một đường đi từ \((0,0)\) đến \((H-1,W-1)\).

Các subtask

Subtask	Điểm	Ràng buộc bổ sung
1	6	Không có ô chướng ngại vật trong mê cung.
2	10	\(H=2\).
3	18	Có đúng một đường đi giữa mỗi cặp ô trống.
4	20	Mỗi đường đi ngắn nhất từ \((0,0)\) đến \((H-1,W-1)\) có độ dài \(H+W-2\).
5	46	Không có ràng buộc nào thêm.

Nếu trong bất kỳ test nào, lời gọi set_instruction hoặc quá trình thực thi chương trình Pulibot không tuân theo các ràng buộc trong mục Chi tiết cài đặt, điểm của lời giải cho subtask đó là \(0\).

Trong mỗi subtask, bạn có thể đạt điểm thành phần bằng cách tạo một cách tô màu gần đúng. Cụ thể:

• Lời giải của một test là đầy đủ nếu cách tô màu cuối cùng của các ô trống thỏa mãn các quy tắc Cuộc thi Robot.
• Lời giải của một test là một phần nếu cách tô màu cuối cùng thỏa mãn tất cả điều kiện sau: tồn tại một đường đi ngắn nhất từ \((0,0)\) đến \((H-1,W-1)\) mà mọi ô trên đường đi có màu \(1\); không có ô trống nào khác trong lưới có màu \(1\); có ô trống trong lưới mang màu khác \(0\) và \(1\).

Nếu lời giải cho một test không phải đầy đủ hay một phần, điểm của test đó là \(0\).

Trong các subtask \(1\)–\(4\), lời giải đầy đủ được \(100\%\) và lời giải một phần cho một test được \(50\%\) số điểm của subtask đó.

Trong subtask \(5\), điểm phụ thuộc vào số màu dùng trong chương trình Pulibot. Cụ thể, gọi \(Z^\star\) là giá trị lớn nhất của \(Z\) trong tất cả các lời gọi set_instruction. Điểm của test được tính theo bảng sau:

Điều kiện	Điểm đầy đủ	Điểm một phần
\(11\le Z^\star\le 19\)	\(20+(19-Z^\star)\)	\(12+(19-Z^\star)\)
\(Z^\star=10\)	31	23
\(Z^\star=9\)	34	26
\(Z^\star=8\)	38	29
\(Z^\star=7\)	42	32
\(Z^\star\le 6\)	46	36

Điểm của mỗi subtask là điểm nhỏ nhất trong các test thuộc subtask đó.

Trình chấm mẫu

Trình chấm mẫu đọc dữ liệu vào theo định dạng sau:

dòng 1: H W
dòng 2 + r (0 ≤ r < H): m[r][0] m[r][1] … m[r][W − 1]

Ở đây, \(m\) là mảng gồm \(H\) mảng, mỗi mảng có \(W\) số nguyên, mô tả các ô không phải ô biên giới. \(m[r][c]=0\) nếu ô \((r,c)\) trống và \(m[r][c]=1\) nếu đó là ô chướng ngại vật.

Trình chấm mẫu trước tiên gọi program_pulibot(). Nếu phát hiện vi phạm giao thức, trình chấm in Protocol Violation: <MSG> rồi kết thúc, trong đó <MSG> là một trong các thông báo sau:

• Invalid array: điều kiện \(-2\le S[i]\le Z_{MAX}\) không thỏa mãn với một \(i\) nào đó, hoặc độ dài \(S\) khác \(5\).
• Invalid color: điều kiện \(0\le Z\le Z_{MAX}\) không thỏa mãn.
• Invalid action: ký tự \(A\) không thuộc H, W, S, E, N, T.
• Same state array: set_instruction được gọi với cùng mảng \(S\) ít nhất hai lần.

Nếu không, sau khi program_pulibot hoàn thành, trình chấm mẫu thực thi chương trình Pulibot trên mê cung trong dữ liệu vào.

Trình chấm mẫu tạo hai kết quả ra. Thứ nhất, trình chấm ghi nhật ký các hành động của Pulibot vào tệp robot.bin trong thư mục làm việc. Tệp này là dữ liệu vào cho công cụ trực quan hóa được mô tả ở phần sau.

Thứ hai, nếu chương trình Pulibot không kết thúc thành công, trình chấm mẫu in một trong các thông báo sau:

• Unexpected state: Pulibot nhận dạng một mảng trạng thái chưa được dùng trong lời gọi set_instruction.
• Invalid move: một hành động khiến Pulibot di chuyển đến ô không trống.
• Too many steps: Pulibot đã thực hiện \(500\,000\) bước mà chưa kết thúc chương trình.

Nếu không, gọi \(e[r][c]\) là trạng thái ô \((r,c)\) sau khi chương trình kết thúc. Trình chấm mẫu in \(H\) dòng theo định dạng:

dòng 1 + r (0 ≤ r < H): e[r][0] e[r][1] … e[r][W − 1]

Công cụ hiển thị

Gói đính kèm của bài toán có tệp display.py. Khi được gọi, chương trình Python này hiển thị các hành động của Pulibot trong mê cung được mô tả bởi dữ liệu vào của trình chấm mẫu. Để thực hiện điều này, tệp nhị phân robot.bin phải có trong thư mục làm việc.

Để gọi chương trình, chạy lệnh sau:

python3 display.py

Một giao diện đồ họa đơn giản sẽ xuất hiện, với các tính năng chính sau:

• Quan sát trạng thái toàn bộ mê cung. Vị trí hiện tại của Pulibot được đánh dấu bằng hình chữ nhật.
• Duyệt qua các bước của Pulibot bằng nút mũi tên hoặc phím nóng tương ứng. Bạn cũng có thể chuyển đến một bước cụ thể.
• Bước tiếp theo được hiển thị ở phía dưới, gồm mảng trạng thái hiện tại và lệnh sẽ thực hiện. Sau bước cuối, giao diện hiển thị một thông báo lỗi của trình chấm hoặc Terminated nếu chương trình kết thúc thành công.
• Với mỗi số biểu diễn một màu, bạn có thể gán một màu nền trực quan và một văn bản hiển thị. Văn bản này là một xâu ngắn xuất hiện trong mỗi ô mang màu đó. Bạn có thể gán màu nền và văn bản bằng hộp thoại mở ra khi nhấn Colors, hoặc bằng cách chỉnh sửa tệp colors.txt.
• Dùng nút Reload để tải lại robot.bin. Điều này hữu ích khi nội dung tệp đã thay đổi.

---

Nguồn: Olympic Tin học Quốc tế 2023 (IOI 2023). Bản dịch tiếng Việt chính thức của đoàn Việt Nam, được đối chiếu với đề tiếng Anh chính thức. Nội dung đề được phát hành theo giấy phép CC BY.