IOI 2011 - Ngày 2

Nhà khảo cổ Benjamas đang chạy thoát thân sau khi khám phá thành phố ngầm bí ẩn của Cá Sấu. Thành phố có \(N\) căn phòng và \(M\) hành lang hai chiều, mỗi hành lang nối một cặp phòng khác nhau gồm hai phòng phân biệt. Thời gian chạy qua các hành lang có thể khác nhau. Trong số \(N\) căn phòng, chỉ có \(K\) phòng là lối ra cho phép cô thoát khỏi thành phố. Benjamas bắt đầu ở phòng \(0\) và muốn đến một phòng có lối ra nhanh nhất có thể.

Tên gác cổng Cá Sấu muốn ngăn Benjamas trốn thoát. Từ hang của mình, hắn điều khiển các cánh cửa bí mật để chặn một hành lang bất kỳ. Tại mỗi thời điểm chỉ một hành lang có thể bị chặn: mỗi khi chặn một hành lang mới, hắn phải mở lại hành lang đã chặn trước đó.

Mỗi lần Benjamas định rời một căn phòng, Cá Sấu có thể chọn chặn một hành lang kề với phòng đó. Sau đó, Benjamas chọn một hành lang không bị chặn và đi theo nó đến phòng tiếp theo. Khi cô đã đi vào một hành lang, Cá Sấu không được chặn hành lang ấy cho đến khi cô đến đầu bên kia. Khi cô vào phòng tiếp theo, hắn lại có thể chọn chặn một hành lang đi ra khỏi phòng đó, kể cả hành lang cô vừa đi qua. Quá trình cứ tiếp tục như vậy.

Benjamas muốn chuẩn bị trước một kế hoạch thoát hiểm đơn giản: một tập hợp chỉ dẫn cho biết phải làm gì khi đến từng căn phòng. Xét phòng \(A\). Nếu đó là phòng có lối ra thì không cần chỉ dẫn, vì cô có thể thoát khỏi thành phố ngay. Nếu không, chỉ dẫn cho phòng \(A\) phải có một trong hai dạng sau:

• “Nếu đến phòng \(A\), hãy đi theo hành lang dẫn đến phòng \(B\). Tuy nhiên, nếu hành lang đó bị chặn thì hãy đi theo hành lang dẫn đến phòng \(C\).”
• “Không cần quan tâm đến phòng \(A\); nếu làm theo kế hoạch này thì không thể đến phòng đó.”

Trong một số trường hợp, chẳng hạn khi kế hoạch khiến Benjamas chạy theo một chu trình, Cá Sấu có thể ngăn cô đến lối ra. Một kế hoạch thoát hiểm được gọi là tốt nếu nó bảo đảm Benjamas đến một phòng có lối ra sau một khoảng thời gian hữu hạn, bất kể Cá Sấu hành động như thế nào. Với một kế hoạch tốt, gọi \(T\) là thời gian nhỏ nhất sao cho chắc chắn Benjamas đã đến một lối ra sau thời gian \(T\). Khi đó, ta nói kế hoạch ấy cần thời gian \(T\).

Yêu cầu

Hãy cài đặt hàm có khai báo chính xác trong crocodile.h:

int travel_plan(int N, int M, int R[][2], int L[], int K, int P[]);

Các tham số có ý nghĩa như sau:

• N: số phòng, được đánh số từ \(0\) đến \(N-1\).
• M: số hành lang, được đánh số từ \(0\) đến \(M-1\).
• R: mảng số nguyên hai chiều mô tả các hành lang. Với \(0 \le i < M\), hành lang \(i\) nối hai phòng phân biệt R[i][0] và R[i][1]. Không có hai hành lang cùng nối một cặp phòng.
• L: mảng số nguyên một chiều chứa thời gian đi qua các hành lang. Với \(0 \le i < M\), L[i] là thời gian Benjamas cần để chạy qua hành lang \(i\) và \(1 \le L[i] \le 1\,000\,000\,000\).
• K: số phòng có lối ra, với \(1 \le K < N\).
• P: mảng một chiều gồm \(K\) số nguyên phân biệt mô tả các phòng có lối ra. Với \(0 \le i < K\), P[i] là số hiệu phòng có lối ra thứ \(i\). Phòng \(0\) không bao giờ là phòng có lối ra.

Hàm phải trả về thời gian \(T\) nhỏ nhất mà một kế hoạch thoát hiểm tốt có thể đạt được.

Ràng buộc

Mỗi phòng không có lối ra có ít nhất hai hành lang đi ra. Mỗi bộ dữ liệu đều có một kế hoạch thoát hiểm tốt với \(T \le 1\,000\,000\,000\).

Phân nhóm

Giới hạn và giao diện

Giới hạn thời gian CPU là 2 giây; giới hạn bộ nhớ là 256 MB. Không có giới hạn riêng cho ngăn xếp; bộ nhớ ngăn xếp được tính vào tổng bộ nhớ sử dụng.

Thư mục cài đặt là crocodile/. Thí sinh cài đặt crocodile.c, crocodile.cpp hoặc crocodile.pas. Giao diện phía thí sinh là crocodile.h hoặc crocodile.pas; giao diện phía trình chấm là crocodile.h hoặc crocodilelib.pas. Trình chấm mẫu gồm grader.c, grader.cpp, hoặc grader.pas cùng với crocodilelib.pas.

Dữ liệu vào

Trình chấm mẫu đọc các tệp grader.in.1, grader.in.2, ... theo định dạng:

• Dòng \(1\): ba số nguyên \(N\), \(M\), \(K\).
• Các dòng \(2\) đến \(M+1\): với \(0 \le i < M\), dòng \(i+2\) chứa R[i][0], R[i][1], L[i], cách nhau bởi dấu cách.
• Dòng \(M+2\): \(K\) số nguyên P[0], P[1], ..., P[K-1], cách nhau bởi dấu cách.
• Dòng \(M+3\): đáp án mong đợi.

Dữ liệu ra

Các tệp kết quả mẫu grader.expect.1, grader.expect.2, ... đều chứa đúng dòng Correct. khi hàm trả về đáp án đúng.

Ví dụ

5 4 3
0 1 2
0 2 3
3 2 1
2 4 4
1 3 4
7

Correct.

5 7 2
0 2 4
0 3 3
3 2 2
2 1 10
0 1 100
0 4 7
3 4 9
1 3
14

Correct.

Nguồn

IOI 2011, ngày thi 2, Pattaya, Thái Lan. Đề Crocodile’s Underground City, bản tiếng Anh 1.3: PDF chính thức. Nội dung được dịch từ đề chính thức; tất cả các hình minh họa đều lấy từ đề chính thức. Giao diện C/C++ và dữ liệu của trình chấm mẫu được đối chiếu với bộ API gốc.

“Những chú voi nhảy múa” là một buổi biểu diễn ngoạn mục ở Pattaya, với \(N\) chú voi nhảy múa trên một đường thẳng được gọi là sân khấu. Sau nhiều năm huấn luyện, các chú voi có thể thực hiện nhiều điệu múa đáng kinh ngạc. Buổi biểu diễn gồm một chuỗi tiết mục. Trong mỗi tiết mục, đúng một chú voi biểu diễn một điệu múa đáng yêu và có thể di chuyển đến một vị trí khác.

Những người tổ chức muốn làm một cuốn sách ảnh ghi lại toàn bộ buổi biểu diễn. Sau mỗi tiết mục, họ muốn chụp tất cả các chú voi theo góc nhìn của khán giả. Tại bất kỳ thời điểm nào, nhiều chú voi có thể ở cùng một vị trí; khi đó, chúng đứng sau nhau tại vị trí ấy.

Một máy ảnh có thể chụp một nhóm voi khi và chỉ khi vị trí của tất cả các chú voi trong nhóm nằm trên một đoạn thẳng có độ dài \(L\), tính cả hai đầu mút. Vì các chú voi có thể đứng rải rác trên sân khấu, có thể cần nhiều máy ảnh để đồng thời chụp được tất cả các chú voi.

Trong bài toán tương tác này, bạn phải xác định số máy ảnh ít nhất cần dùng sau mỗi tiết mục. Số máy ảnh cần dùng có thể tăng, giảm hoặc giữ nguyên giữa hai tiết mục.

Yêu cầu

Hãy cài đặt hai hàm có khai báo chính xác trong elephants.h:

void init(int N, int L, int X[]);
int update(int i, int y);

Hàm init(N,L,X) nhận số voi N, độ dài đoạn thẳng L mà một máy ảnh chụp được và mảng số nguyên một chiều X mô tả vị trí ban đầu. Các chú voi được đánh số từ \(0\) đến \(N-1\). Độ dài L là số nguyên thỏa mãn \(0 \le L \le 1\,000\,000\,000\). Với \(0 \le i < N\), chú voi \(i\) bắt đầu ở vị trí X[i]. Các vị trí ban đầu đã được sắp xếp theo thứ tự không giảm:

Trong lúc nhảy múa, thứ tự các chú voi có thể thay đổi. Hàm init chỉ được gọi một lần, trước tất cả các lần gọi update, và không trả về giá trị.

Hàm update(i,y) nhận số hiệu i của chú voi di chuyển trong tiết mục hiện tại và vị trí y của chú voi ấy sau tiết mục. Ta có \(0 \le i < N\) và y là số nguyên thỏa mãn \(0 \le y \le 1\,000\,000\,000\). Hàm được gọi nhiều lần; mỗi lần ứng với một tiết mục diễn ra tiếp sau tất cả các tiết mục trước đó. Mỗi lần gọi phải trả về số máy ảnh ít nhất cần dùng để chụp tất cả các chú voi sau tiết mục tương ứng.

Ràng buộc

Các giới hạn của \(L\), các vị trí ban đầu và các vị trí mới nêu trên áp dụng cho mọi nhóm. Nhiều chú voi được phép đứng cùng vị trí, trừ khi nhóm quy định các vị trí phải phân biệt.

Phân nhóm

Giới hạn và giao diện

Giới hạn thời gian CPU là 9 giây. Các cấu trúc chứa phần tử trong thư viện chuẩn C++ (STL) có thể chậm; đặc biệt, việc dùng chúng có thể khiến chương trình không giải được nhóm \(5\) trong thời gian cho phép. Giới hạn bộ nhớ là 256 MB. Không có giới hạn riêng cho ngăn xếp; bộ nhớ ngăn xếp được tính vào tổng bộ nhớ sử dụng.

Thư mục cài đặt là elephants/. Thí sinh cài đặt elephants.c, elephants.cpp hoặc elephants.pas. Giao diện phía thí sinh là elephants.h hoặc elephants.pas. Trình chấm mẫu là grader.c, grader.cpp hoặc grader.pas.

Dữ liệu vào

Trình chấm mẫu đọc các tệp grader.in.1, grader.in.2, ... theo định dạng:

• Dòng \(1\): \(N\), \(L\), \(M\), trong đó \(M\) là số tiết mục.
• Các dòng \(2\) đến \(N+1\): các vị trí ban đầu; dòng \(k+2\) chứa X[k], với \(0 \le k < N\).
• Các dòng \(N+2\) đến \(N+M+1\): thông tin về \(M\) tiết mục. Với \(1 \le j \le M\), dòng \(N+1+j\) chứa i[j], y[j], s[j], cách nhau bởi dấu cách. Các số này cho biết trong tiết mục \(j\), chú voi i[j] chuyển đến vị trí y[j], và số máy ảnh ít nhất cần dùng sau đó là s[j].

Dữ liệu ra

Các tệp kết quả mẫu grader.expect.1, grader.expect.2, ... đều chứa đúng dòng Correct. khi các giá trị trả về đều đúng.

Ví dụ

4 10 2
10
15
17
20
1 32 2
0 7 3

Correct.

4 10 5
10
15
17
20
2 16 1
1 25 2
3 35 2
0 38 2
2 0 3

Correct.

Nguồn

IOI 2011, ngày thi 2, Pattaya, Thái Lan. Đề Dancing Elephants, bản tiếng Anh 1.2: PDF chính thức. Nội dung được dịch từ đề chính thức; tất cả các hình minh họa đều lấy từ đề chính thức. Giao diện C/C++ và dữ liệu của trình chấm mẫu được đối chiếu với bộ API gốc.

Yanee rất yêu thích chim. Kể từ khi đọc về giao thức IP truyền bằng chim đưa thư (IP over Avian Carriers, viết tắt là IPoAC), cô dành nhiều thời gian huấn luyện một đàn vẹt thông minh để mang thông điệp đi xa.

Ước mơ của Yanee là dùng đàn chim để gửi một thông điệp \(M\) đến một vùng đất xa xôi. Thông điệp \(M\) là một dãy gồm \(N\) số nguyên, không nhất thiết phân biệt, mỗi số nằm trong khoảng từ \(0\) đến \(255\), kể cả hai đầu mút. Yanee có \(K\) chú vẹt được huấn luyện đặc biệt. Tất cả đều trông giống nhau nên cô không thể phân biệt chúng. Mỗi chú vẹt có thể nhớ một số nguyên từ \(0\) đến \(R\), kể cả hai đầu mút.

Ban đầu, Yanee thử một cách đơn giản: cô cẩn thận thả từng chú vẹt ra khỏi lồng; trước khi mỗi chú bay đi, cô dạy nó một số trong dãy thông điệp, theo đúng thứ tự. Tiếc rằng cách này không thành công. Cuối cùng, tất cả các chú vẹt đều đến đích, nhưng thứ tự đến không nhất thiết giống thứ tự xuất phát. Yanee có thể khôi phục các số đã gửi nhưng không thể sắp xếp chúng về đúng thứ tự.

Để thực hiện ước mơ, Yanee cần một cách tốt hơn và muốn nhờ bạn giúp đỡ. Với thông điệp \(M\), cô vẫn thả từng chú vẹt như trước. Bạn cần viết chương trình thực hiện hai thao tác riêng biệt:

• Đọc thông điệp \(M\) và biến đổi nó thành một dãy gồm nhiều nhất \(K\) số nguyên từ \(0\) đến \(R\) để dạy cho các chú vẹt.
• Đọc danh sách các số nguyên từ \(0\) đến \(R\) nhận được khi các chú vẹt đến đích, rồi biến đổi danh sách ấy về thông điệp \(M\) ban đầu.

Có thể giả sử mọi chú vẹt luôn đến đích và nhớ chính xác số được giao. Các chú vẹt có thể đến theo thứ tự bất kỳ. Yanee chỉ có \(K\) chú vẹt, vì vậy dãy số bạn tạo ra không được chứa quá \(K\) phần tử.

Yêu cầu

Hãy viết hai hàm riêng biệt: một hàm dùng ở phía gửi (bộ mã hóa) và một hàm dùng ở phía nhận (bộ giải mã). Quá trình tổng thể được minh họa dưới đây: thông điệp ban đầu \(M\) được mã hóa thành \(E\), thứ tự bị xáo trộn thành \(X\), rồi được giải mã để thu lại đúng \(M\).

Trên LQDOJ, nộp một tệp mã nguồn C++ cài đặt cả encode và decode, không cài đặt hàm main. Hai vai trò được chạy trong hai tiến trình riêng biệt: tiến trình mã hóa chỉ được gọi encode, còn tiến trình giải mã chỉ được gọi decode. Biến toàn cục, biến static và mọi trạng thái trong bộ nhớ của tiến trình mã hóa không được chia sẻ với tiến trình giải mã.

Thông tin mà phía giải mã nhận được là N, số lượng L và các giá trị trong X do trình chấm truyền vào. Dãy X có thể là bất kỳ hoán vị nào của các số đã gửi, kể cả khi có các giá trị trùng nhau. Vì vậy, thứ tự gọi send không thể dùng để truyền thông tin; việc giải mã phải đúng với mọi thứ tự nhận. Cách nộp một tệp nguồn này giữ nguyên ý nghĩa của hai vai trò trong đề gốc.

Các khai báo giao diện gốc dưới đây được giữ nguyên:

// encoder.h
void encode(int N, int M[]);

// decoder.h
void decode(int N, int L, int X[]);

Trình chấm cung cấp hai hàm sau để bạn gọi:

// encoderlib.h
void send(int a);

// decoderlib.h
void output(int b);

Hàm encode(N,M) nhận độ dài thông điệp N và mảng một chiều M gồm \(N\) số nguyên, với \(0 \le M[i] \le 255\) cho mọi \(0 \le i < N\). Hàm phải mã hóa thông điệp thành một dãy số nguyên trong đoạn \([0,R]\) để gửi bằng vẹt. Để báo dãy này, encode phải gọi send(a) một lần cho mỗi số nguyên a muốn giao cho một chú vẹt.

Hàm decode(N,L,X) nhận độ dài thông điệp ban đầu N, độ dài thông điệp nhận được L (số vẹt đã gửi), và mảng một chiều X gồm \(L\) số nguyên nhận được. Các phần tử X[i], với \(0 \le i < L\), chính là các số do encode tạo ra, nhưng có thể đã bị đổi thứ tự. Hàm phải khôi phục thông điệp ban đầu và báo kết quả bằng cách gọi output(b) cho từng số nguyên b trong thông điệp đã giải mã, theo đúng thứ tự.

\(R\) và \(K\) không được truyền vào các hàm. Giá trị của chúng được quy định trong từng nhóm bên dưới. Để giải đúng một nhóm, chương trình phải thỏa mãn tất cả các điều kiện sau:

• Mọi số nguyên do encode gửi đều nằm trong phạm vi quy định của nhóm.
• Số lần encode gọi send không vượt quá \(K\) của nhóm. Lưu ý rằng \(K\) phụ thuộc vào độ dài thông điệp.
• decode khôi phục đúng thông điệp ban đầu và gọi output đúng \(N\) lần, lần lượt với các giá trị M[0], M[1], ..., M[N-1].

Ở nhóm cuối, điểm số phụ thuộc vào tỉ số giữa độ dài thông điệp đã mã hóa và độ dài thông điệp ban đầu.

Ràng buộc

Trong mọi nhóm, các phần tử của thông điệp ban đầu là số nguyên từ \(0\) đến \(255\), trừ ràng buộc chặt hơn của nhóm \(1\). Phạm vi số được gửi luôn bao gồm cả \(0\) và \(R\).

Phân nhóm

Cách tính điểm nhóm 5. Với bộ dữ liệu \(t\), gọi \(N_t\) là độ dài thông điệp ban đầu và \(L_t\) là độ dài thông điệp đã mã hóa. Đặt:

Giá trị lớn nhất được lấy trên tất cả các bộ dữ liệu của nhóm \(5\). Điểm của nhóm được tính như sau:

• Nếu \(P \le 5\), bạn được trọn \(19\) điểm.
• Nếu \(5 < P \le 6\), bạn được \(18\) điểm.
• Nếu \(6 < P \le 7\), bạn được \(17\) điểm.
• Nếu \(7 < P \le 15\), bạn được số điểm sau, làm tròn xuống đến số nguyên gần nhất:

• Nếu \(P>15\) hoặc có bất kỳ kết quả nào không đúng, bạn được \(0\) điểm.

Một lời giải hợp lệ cho bất kỳ nhóm nào từ \(1\) đến \(4\) cũng giải được tất cả các nhóm đứng trước nó. Tuy nhiên, do giới hạn \(K\) lớn hơn, một lời giải hợp lệ cho nhóm \(5\) có thể không giải được các nhóm \(1\) đến \(4\). Có thể dùng cùng một lời giải để giải tất cả các nhóm.

Giới hạn và giao diện

Trong môi trường chấm của IOI 2011, bài làm được biên dịch thành hai chương trình e và d, chạy riêng biệt. Cả mô-đun mã hóa lẫn mô-đun giải mã đều được liên kết vào mỗi chương trình, nhưng e chỉ gọi encode, còn d chỉ gọi decode.

Chương trình e thực hiện 50 lần gọi encode trong 2 giây CPU. Chương trình d thực hiện 50 lần gọi decode trong 2 giây CPU. Giới hạn bộ nhớ là 256 MB. Không có giới hạn riêng cho ngăn xếp; bộ nhớ ngăn xếp được tính vào tổng bộ nhớ sử dụng.

Trong bộ API gốc của IOI 2011, thư mục cài đặt là parrots/. Thí sinh cài đặt encoder.c, encoder.cpp hoặc encoder.pas, và decoder.c, decoder.cpp hoặc decoder.pas. Giao diện phía thí sinh là encoder.h hoặc encoder.pas, cùng với decoder.h hoặc decoder.pas. Giao diện phía trình chấm là encoderlib.h hoặc encoderlib.pas, cùng với decoderlib.h hoặc decoderlib.pas. Trình chấm mẫu là grader.c, grader.cpp hoặc grader.pas.

Trong cách tổ chức hai tệp của bộ API gốc, với C/C++, cả trình chấm mẫu lẫn trình chấm chính thức đều liên kết encoder.c[pp] và decoder.c[pp] cùng với trình chấm. Vì vậy, cần khai báo các biến toàn cục trong mỗi tệp là static để tránh xung đột với biến trong tệp khác.

Trình chấm mẫu trong bộ API gốc thực hiện hai lượt riêng biệt. Trong mỗi lượt, nó gọi encode với dữ liệu đã cho rồi gọi decode với kết quả của encode. Ở lượt đầu, nó giữ nguyên thứ tự các số đã mã hóa. Ở lượt thứ hai, nó đổi chỗ các số ở các vị trí lẻ và chẵn kề nhau. Trình chấm chính thức áp dụng nhiều kiểu hoán vị khác nhau. Bạn có thể thay đổi cách xáo trộn của trình chấm mẫu bằng cách sửa hàm shuffle trong C/C++ hoặc Shuffle trong Pascal.

Trình chấm mẫu kiểm tra cả phạm vi giá trị lẫn độ dài dữ liệu mã hóa. Mặc định, nó kiểm tra các số nằm trong đoạn \([0,65\,535]\) và độ dài không quá \(10N\). Bạn có thể thay đổi các hằng số channel_range (chẳng hạn từ \(65\,535\) thành \(255\)) và max_expansion (chẳng hạn từ \(10\) thành \(15\) hoặc \(7\)).

Dữ liệu vào

Trình chấm mẫu đọc các tệp grader.in.1, grader.in.2, ... theo định dạng:

• Dòng \(1\): \(N\).
• Dòng \(2\): \(N\) số M[0], M[1], ..., M[N-1].

Dữ liệu ra

Các tệp kết quả mẫu grader.expect.1, grader.expect.2, ... đều chứa đúng dòng Correct. khi kết quả giải mã đúng và dữ liệu mã hóa thỏa mãn các giới hạn mà trình chấm mẫu kiểm tra.

Ví dụ

3
10 30 20

Correct.

send(7)
send(3)
send(2)
send(70)
send(15)
send(20)
send(3)

output(10)
output(30)
output(20)

8
1 0 1 0 0 1 1 0

Correct.

10
1 1 2 1 2 3 1 7 10 9

Correct.

Nguồn

IOI 2011, ngày thi 2, Pattaya, Thái Lan. Đề Parrots, bản tiếng Anh 1.3: PDF chính thức. Nội dung được dịch từ đề chính thức; tất cả các hình minh họa đều lấy từ đề chính thức. Giao diện C/C++ và dữ liệu của trình chấm mẫu được đối chiếu với bộ API gốc.