Công ty chuyển phát Xedef vận chuyển kiện hàng bằng máy bay giữa một số thành phố. Một số thành phố là trung tâm của Xedef, có cơ sở xử lý hàng chuyên dụng. Mỗi máy bay bay qua lại giữa một cặp thành phố và có thể chở hàng theo cả hai chiều.

Để chuyển một kiện hàng giữa hai thành phố, cần đưa nó qua một chuỗi chặng bay; mỗi chặng nối hai thành phố có máy bay phục vụ. Chuỗi này phải đi qua ít nhất một trung tâm của Xedef. Để định tuyến, Xedef muốn ghi trên nhãn của mỗi kiện hàng thông tin mã hóa về số chặng ít nhất từ mỗi thành phố tới mỗi trung tâm. Số chặng từ một trung tâm đến chính nó bằng 0. Thông tin phải được biểu diễn thật gọn.

Yêu cầu cài đặt

Bạn phải cài đặt hai hàm sau:

void encode(int N, int H, int P, int A[], int B[]);
void decode(int N, int H);

N là số thành phố, đánh số từ 0 đến N-1; H là số trung tâm, chính là các thành phố từ 0 đến H-1. Có P cặp thành phố được nối bằng máy bay. Các cặp không thứ tự đều khác nhau. Hai mảng A, B có P phần tử, với cặp thứ i là (A[i], B[i]).

encode phải tạo một dãy bit để từ đó decode xác định được số chặng ít nhất từ mọi thành phố đến mọi trung tâm. Các hàm sau do trình chấm cung cấp:

void encode_bit(int b);
int decode_bit();
void hops(int h, int c, int d);

encode gửi từng bit bằng encode_bit(b), với b bằng 0 hoặc 1. Lần gọi decode_bit() thứ \(i\) trả về bit được gửi trong lần gọi encode_bit thứ \(i\). Số lần gọi decode_bit không được vượt quá số bit đã gửi; không bắt buộc phải đọc hết các bit.

Sau khi giải mã, decode phải gọi hops(h,c,d) cho mọi cặp trung tâm h và thành phố c, kể cả c=h, với d là số chặng ít nhất từ h đến c. Phải có đúng N*H lời gọi, mỗi cặp đúng một lần; thứ tự tùy ý. Bảo đảm có thể đi từ mỗi trung tâm tới mọi thành phố.

Hai hàm chỉ được truyền thông tin qua giao diện quy định. Cấm dùng biến chung giữa hai giai đoạn, truy cập tệp hoặc mạng để truyền thông tin. Trong C/C++, có thể dùng biến static để giữ dữ liệu riêng của bộ mã hóa hoặc giải mã; trong Pascal có thể khai báo trong phần implementation. Trên LQDOJ, hai hàm chạy trong hai tiến trình riêng biệt: bộ giải mã không nhận mạng đường bay hay trạng thái bộ nhớ của bộ mã hóa.

Dữ liệu vào

Chương trình nhận dữ liệu qua tham số hàm và decode_bit, không đọc đầu vào chuẩn. Trong trình chấm mẫu chính thức, dòng đầu chứa N P H; P dòng tiếp theo chứa các cặp A[i] B[i]; H*N dòng sau là các khoảng cách đúng, theo thứ tự trung tâm rồi thành phố. Khoảng cách từ trung tâm i tới thành phố j nằm ở dòng thứ i*N+j+1 của phần này. Các khoảng cách đúng chỉ dành cho trình chấm.

Dữ liệu ra

Không in kết quả. encode gửi bit bằng encode_bit; decode báo kết quả bằng hops. Trình chấm mẫu chính thức ghi OK 1, OK 2, OK 3, OK 4 tương ứng với các nhóm mà lời giải vượt qua.

Ràng buộc

\(1\le N\le1000\); \(1\le H\le\min(N,36)\); các thành phố trong A, B thuộc \([0,N-1]\). Không có cặp trùng lặp hoặc cặp nối một thành phố với chính nó. Đồ thị liên thông, do đó \(N-1\le P\le N(N-1)/2\). Mỗi lần gọi hops phải có \(0\le h<H\), \(0\le c<N\) và khoảng cách đúng \(0\le d<N\).

Phân nhóm

Mọi nhóm có cùng ràng buộc về mạng đường bay. Mỗi nhóm chỉ có điểm khi giải mã đúng toàn bộ các bộ kiểm tra và không vượt giới hạn bit trên bất kỳ bộ nào.

Ví dụ

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

Chi tiết triển khai

Gói LQDOJ nhận một tệp C++ cài đặt cả encode và decode, không viết main. saveit.h khai báo đầy đủ các hàm; các tên encoder.h, decoder.h, grader.h trong templates.zip cũng giữ giao diện chính thức. Trình chấm biên dịch cùng stub.cpp và khởi chạy riêng bộ mã hóa, bộ giải mã.

Trong môi trường gốc, thư mục là /home/ioi2010-contestant/saveit/; thí sinh cài đặt encoder.c/.cpp/.pas và decoder.c/.cpp/.pas, với các giao diện encoder.h/.pas, decoder.h/.pas, grader.h hoặc graderlib.pas. Trình chấm mẫu là grader.c/.cpp/.pas cùng graderlib.pas. Lệnh runc/submit và phím Control-R/Control-J thuộc môi trường năm 2010; trên LQDOJ nộp tệp C++ như trên.

Nguồn

IOI 2010, ngày 2, bài 4 — Saveit. Đề chính thức, PDF tiếng Anh.