Leonardo rất hăng hái khi thực hiện Bữa tối cuối cùng, bức tranh tường nổi tiếng nhất của ông. Một trong những công việc đầu tiên mỗi ngày là quyết định các màu keo sẽ dùng trong phần còn lại của ngày. Ông cần nhiều màu nhưng chỉ có thể giữ một số lượng hạn chế trên giàn giáo. Người trợ lý có nhiệm vụ trèo lên đưa màu cho ông rồi trèo xuống đặt những màu được trả lại lên kệ dưới sàn.
Bạn phải viết hai chương trình riêng biệt để giúp người trợ lý. Chương trình thứ nhất nhận toàn bộ dãy màu Leonardo sẽ cần trong ngày và tạo ra một xâu bit ngắn gọi là chỉ dẫn. Trong ngày, người trợ lý chỉ có chỉ dẫn này, không được biết trước các yêu cầu tương lai. Chương trình thứ hai nhận chỉ dẫn rồi nhận và xử lý từng yêu cầu một; nó phải hiểu chỉ dẫn để đưa ra các lựa chọn tối ưu.
Di chuyển màu giữa kệ và giàn giáo
Có \(N\) màu, đánh số từ \(0\) đến \(N-1\). Mỗi ngày Leonardo yêu cầu màu đúng \(N\) lần. Gọi \(C\) là dãy \(N\) yêu cầu, mỗi phần tử thuộc \(0,\ldots,N-1\). Một màu có thể không xuất hiện trong \(C\), hoặc xuất hiện nhiều lần.
Giàn giáo luôn đầy và chứa \(K\) trong số \(N\) màu, với \(K<N\). Ban đầu, giàn giáo chứa các màu từ \(0\) đến \(K-1\), kể cả hai đầu. Các yêu cầu được xử lý lần lượt. Nếu màu được yêu cầu đã có trên giàn giáo, người trợ lý được nghỉ. Nếu chưa có, anh ta phải lấy màu đó từ kệ đưa lên giàn giáo, đồng thời chọn một màu đang có trên giàn giáo để mang xuống kệ vì không còn chỗ cho màu mới.
Chiến thuật tối ưu của Leonardo
Người trợ lý muốn được nghỉ nhiều lần nhất. Mỗi khi phải đưa một màu xuống kệ, lựa chọn của anh ta có thể ảnh hưởng đến các yêu cầu về sau. Nếu biết trước \(C\), Leonardo chỉ ra cách chọn màu cần loại khỏi giàn giáo bằng cách xét những màu đang có và phần yêu cầu còn lại:
- Nếu có màu trên giàn giáo sẽ không bao giờ được yêu cầu nữa, chọn một màu như vậy để đưa xuống kệ.
- Nếu không, chọn màu có lần được yêu cầu tiếp theo xa nhất trong tương lai. Cụ thể, tìm lần xuất hiện đầu tiên trong tương lai của từng màu đang trên giàn giáo, rồi loại màu có lần xuất hiện đó muộn nhất.
Có thể chứng minh chiến thuật này giúp người trợ lý được nghỉ nhiều lần nhất có thể.
Trí nhớ hạn chế
Vào buổi sáng, người trợ lý xin Leonardo viết \(C\) lên giấy để xác định và làm theo chiến thuật tối ưu. Nhưng Leonardo muốn giữ bí mật kỹ thuật làm việc nên không cho anh ta giữ tờ giấy; ông chỉ cho đọc \(C\) và cố nhớ. Trí nhớ của người trợ lý rất kém, chỉ nhớ được tối đa \(M\) bit, thường không đủ để tái tạo toàn bộ \(C\). Anh ta cần tìm cách tính một dãy bit thích hợp để nhớ; dãy chỉ dẫn này được ký hiệu là \(A\).
Yêu cầu và giao thức
Bạn phải viết hai chương trình riêng biệt bằng cùng một ngôn ngữ lập trình. Chúng được thực hiện nối tiếp nhau và không được liên lạc với nhau trong khi chạy. Chương trình đầu tiên dùng vào buổi sáng, nhận \(C\) và tạo \(A\). Chương trình thứ hai dùng trong ngày, nhận \(A\), rồi xử lý \(C\) theo từng yêu cầu: phải xử lý xong yêu cầu hiện tại trước khi nhận yêu cầu tiếp theo.
Trong chương trình thứ nhất, cài đặt ComputeAdvice(C, N, K, M). Đầu vào là mảng \(C\) gồm \(N\) số nguyên thuộc \(0,\ldots,N-1\), số màu \(K\) trên giàn giáo và số bit chỉ dẫn tối đa \(M\). Chương trình tạo dãy \(A\) dài không quá \(M\) bit, rồi gửi các bit theo đúng thứ tự bằng chương trình con được cung cấp:
WriteAdvice(B): nối bit \(B\) vào cuối dãy chỉ dẫn \(A\) hiện tại. Được gọi nhiều nhất \(M\) lần.
Trong chương trình thứ hai, cài đặt Assist(A, N, K, R). Đầu vào gồm dãy chỉ dẫn \(A\), các số \(N,K\) như trên, và độ dài thực tế \(R\) của \(A\) tính bằng bit, với \(R \le M\). Chương trình thực hiện chiến thuật của người trợ lý bằng các chương trình con được cung cấp:
GetRequest(): trả về màu tiếp theo Leonardo yêu cầu; không tiết lộ thông tin về các yêu cầu tương lai.PutBack(T): đưa màu \(T\) từ giàn giáo xuống kệ. Chỉ được gọi khi \(T\) là một màu hiện có trên giàn giáo.
Assist phải gọi GetRequest đúng \(N\) lần, nhận các yêu cầu theo thứ tự. Sau mỗi lần gọi, nếu màu nhận được chưa có trên giàn giáo, phải gọi PutBack(T) với màu được chọn để nhường chỗ cho màu vừa yêu cầu. Nếu màu đã có trên giàn giáo, không được gọi PutBack. Vi phạm quy tắc này bị coi là lỗi và chương trình sẽ bị kết thúc. Nhớ rằng giàn giáo ban đầu chứa các màu \(0,\ldots,K-1\).
Một bộ dữ liệu được coi là giải đúng nếu cả hai chương trình con tuân thủ mọi ràng buộc và tổng số lần gọi PutBack đúng bằng số lần của chiến thuật tối ưu của Leonardo. Nếu nhiều chiến thuật đạt cùng số lần gọi tối ưu, được dùng bất kỳ chiến thuật nào; không bắt buộc thực hiện đúng từng lựa chọn của Leonardo.
Chi tiết cài đặt
Trên LQDOJ, nộp đúng một tệp C hoặc C++ cài đặt cả ComputeAdvice và Assist. Trình chấm chạy hai phần trong hai tiến trình tách biệt: tiến trình thứ nhất gọi ComputeAdvice, còn tiến trình thứ hai chỉ nhận dãy chỉ dẫn rồi gọi Assist. Vì vậy, biến toàn cục và bộ nhớ của hai phần không được chia sẻ; cách duy nhất để truyền thông tin từ ComputeAdvice sang Assist là gọi WriteAdvice để tạo dãy chỉ dẫn nhận qua tham số A.
C/C++
C++void ComputeAdvice(int *C, int N, int K, int M);
void WriteAdvice(unsigned char a);
void Assist(unsigned char *A, int N, int K, int R);
void PutBack(int T);
int GetRequest();
Các chương trình con phải hoạt động như đã mô tả. Có thể viết thêm các chương trình con dùng nội bộ, nhưng nên khai báo chúng là static hoặc bảo đảm tên không trùng nhau. Bài nộp không được giao tiếp với đầu vào, đầu ra chuẩn hay tệp tin. Tệp supper.h, trình chấm mẫu và script biên dịch C/C++ được cung cấp trong phần đính kèm. Mã nguồn cần bắt đầu bằng:
Dữ liệu vào
Trình chấm mẫu nhận dữ liệu như sau:
- Dòng \(1\):
N K M.
- Các dòng \(2,\ldots,N+1\): mỗi dòng chứa \(C[i]\), theo thứ tự \(i=0,\ldots,N-1\).
Dữ liệu ra và hành vi của trình chấm mẫu
Trình chấm mẫu chạy ComputeAdvice trước và tạo tệp advice.txt, chứa từng bit chỉ dẫn, cách nhau bởi dấu cách và kết thúc bằng số 2. Sau đó, trình chấm chạy Assist và tạo đầu ra mà mỗi dòng có dạng R [number] hoặc P [number]. Dòng R [number] biểu thị lời gọi GetRequest() và giá trị nhận được; dòng P [number] biểu thị lời gọi PutBack() và màu được đưa xuống kệ. Đầu ra kết thúc bằng một dòng E.
Thời gian chạy với trình chấm chính thức có thể hơi khác thời gian trên máy cục bộ. Chênh lệch này không đáng kể, nhưng nên dùng giao diện chạy thử để kiểm tra lời giải có nằm trong giới hạn thời gian hay không.
Ràng buộc
- Có \(N\) màu và đúng \(N\) yêu cầu; \(0 \le C[i] \le N-1\).
- Giàn giáo chứa \(K<N\) màu; ban đầu là các màu \(0,\ldots,K-1\).
- Dãy chỉ dẫn có \(R \le M\) bit.
- Giới hạn thời gian: \(5\) giây.
- Giới hạn bộ nhớ: \(256\) MiB.
Phân nhóm
| Phân nhóm |
Điểm |
Điều kiện |
| 1 |
8 |
\(N \le 5\,000\); được dùng tối đa \(M=65\,000\) bit. |
| 2 |
9 |
\(N \le 100\,000\); được dùng tối đa \(M=2\,000\,000\) bit. |
| 3 |
9 |
\(N \le 100\,000\), \(K \le 25\,000\); được dùng tối đa \(M=1\,500\,000\) bit. |
| 4 |
35 |
\(N \le 5\,000\); được dùng tối đa \(M=10\,000\) bit. |
| 5 |
Tối đa 39 |
\(N \le 100\,000\), \(K \le 25\,000\); được dùng tối đa \(M=1\,800\,000\) bit. |
Điểm phân nhóm \(5\) phụ thuộc vào độ dài chỉ dẫn được gửi. Gọi \(R_{\max}\) là độ dài lớn nhất của dãy chỉ dẫn do ComputeAdvice tạo ra trên tất cả các bộ dữ liệu của phân nhóm. Điểm được tính như sau:
\[
\begin{cases}
39, & R_{\max} \le 200\,000,\\
\dfrac{39(1\,800\,000-R_{\max})}{1\,600\,000}, & 200\,000 < R_{\max} < 1\,800\,000,\\
0, & R_{\max} \ge 1\,800\,000.
\end{cases}
\]
Ví dụ
Ví dụ 1
Input
2 0 3 0
Giải thích
Có \(N=4\) màu, đánh số từ \(0\) đến \(3\), và \(4\) yêu cầu. Giàn giáo chứa được \(K=2\) màu, ban đầu là \([0,1]\). Một cách xử lý là:
- Màu \(2\) chưa có trên giàn giáo. Người trợ lý đưa màu \(2\) lên và đưa màu \(1\) xuống, thu được \([0,2]\).
- Màu \(0\) đã có, nên người trợ lý được nghỉ.
- Để đáp ứng yêu cầu màu \(3\), người trợ lý đưa màu \(0\) xuống, thu được \([3,2]\).
- Yêu cầu cuối là màu \(0\); người trợ lý phải mang nó lên và quyết định đưa màu \(2\) xuống, thu được \([3,0]\).
Cách xử lý trên không tối ưu. Chiến thuật tối ưu của Leonardo đưa màu \(2\) xuống ở bước thứ ba, nhờ đó người trợ lý lại được nghỉ ở bước cuối.
Ví dụ 2
Input
0 0 1 0 0 0 1 0 1 1 1 0 1 1 0 0
Giải thích
Vào buổi sáng, người trợ lý có thể đọc \(C\) và quyết định trước các lựa chọn. Một khả năng là ghi nhớ trạng thái giàn giáo sau mỗi yêu cầu. Với cách xử lý không tối ưu ở Ví dụ 1, các trạng thái là \([0,2]\), \([0,2]\), \([3,2]\), \([3,0]\); trạng thái ban đầu \([0,1]\) đã biết sẵn.
Giả sử \(M=16\). Vì \(N=4\), mỗi màu có thể lưu bằng \(2\) bit, nên \(16\) bit đủ lưu dãy trạng thái trên, tạo ra dãy \(A\) đã cho. Trong ngày, người trợ lý giải mã chỉ dẫn này để đưa ra các lựa chọn. Với \(M=16\), anh ta cũng có thể lưu toàn bộ \(C\) chỉ bằng \(8\) trong \(16\) bit. Ví dụ chỉ minh họa một cách biểu diễn khác; cách xử lý được biểu diễn vẫn là cách không tối ưu đã nêu.
Ví dụ 3
Input
WriteAdvice(0)
WriteAdvice(0)
WriteAdvice(1)
WriteAdvice(0)
WriteAdvice(0)
WriteAdvice(0)
WriteAdvice(1)
WriteAdvice(0)
WriteAdvice(1)
WriteAdvice(1)
WriteAdvice(1)
WriteAdvice(0)
WriteAdvice(1)
WriteAdvice(1)
WriteAdvice(0)
WriteAdvice(0)
Giải thích
Tiếp tục Ví dụ 2, nếu ComputeAdvice tạo \(A=(0,0,1,0,0,0,1,0,1,1,1,0,1,1,0,0)\), thì gửi nó bằng đúng dãy lời gọi trên. Sau đó Assist nhận \(A\), \(N=4\), \(K=2\), \(R=16\) và phải gọi GetRequest đúng \(4\) lần. Sau một số yêu cầu, nó phải gọi PutBack(T) với màu thích hợp.
Bảng dưới đây tương ứng với các lựa chọn không tối ưu trong Ví dụ 1. Dấu gạch ngang nghĩa là không gọi PutBack.
Giá trị do GetRequest() trả về |
Hành động |
| \(2\) |
PutBack(1) |
| \(0\) |
— |
| \(3\) |
PutBack(0) |
| \(0\) |
PutBack(2) |
