Các container
Đề bài
Mô tả
Một bến cảng container lưu giữ các container lớn, sau đó chúng sẽ được xếp lên các tàu biển để vận chuyển ra nước ngoài. Các container đến bến bằng đường bộ và đường sắt được xếp chồng thành các chồng ngay khi chúng đến.
Mỗi tàu biển chở rất nhiều container. Thời gian xếp hàng lên một tàu phụ thuộc một phần vào vị trí các container của tàu đó. Thời gian sẽ tăng lên nếu các container không nằm trên đỉnh các chồng mà chỉ lấy được sau khi đã dỡ bỏ những container khác nằm phía trên chúng.
Bến cảng cần một phương án xếp chồng để giảm thời gian xếp hàng. Phương án phải cho phép xếp hàng lên mỗi tàu mà chỉ cần lấy các container nằm trên cùng của các chồng, đồng thời số chồng cần dùng là ít nhất.
Trong bài này, ta biết thứ tự xếp hàng các tàu và thứ tự các container đến. Mỗi tàu được biểu diễn bằng một chữ cái in hoa từ A đến Z (tính cả hai đầu), và các tàu được xếp hàng theo thứ tự bảng chữ cái. Mỗi container được đánh dấu bằng chữ cái in hoa của con tàu mà nó cần được xếp lên. Một chồng có thể chứa bao nhiêu container cũng được.
Dữ liệu vào
Dữ liệu gồm nhiều bộ test. Mỗi bộ test là một dòng chứa từ đến chữ cái in hoa, cho biết thứ tự đến của một tập container. Ví dụ, dòng ABAC nghĩa là các container đến lần lượt cần được xếp lên các tàu A, B, A và C. Khi tất cả container đã đến, các tàu được xếp hàng theo thứ tự tăng ngặt: đầu tiên là tàu A, rồi đến tàu B, và cứ thế tiếp tục.
Sau bộ test cuối cùng là một dòng chứa từ end.
Dữ liệu ra
Với mỗi bộ test, in số thứ tự bộ test (bắt đầu từ ) và số chồng ít nhất cần dùng để lưu các container trước khi bắt đầu xếp hàng lên tàu. Định dạng kết quả theo đúng ví dụ.
Ràng buộc
- Mỗi bộ test là một xâu gồm đến chữ cái in hoa
A..Z. - Mỗi file có không quá bộ test.
Ví dụ
| Input | Output | Giải thích |
|---|---|---|
| A CBACBACBACBACBA CCCCBBBBAAAA ACMICPC end |
Case 1: 1 Case 2: 3 Case 3: 1 Case 4: 4 |
Bộ 2: ba chồng, mỗi chồng chứa các container của một tàu. Bộ 3: chỉ cần một chồng, A nằm trên cùng, C ở dưới cùng. Bộ 4: có thể dùng chồng, từ dưới lên: A; C; M, I, C; P, C. |
| ABCDEFGHIJKLMNOPQRSTUVWXYZ ZYXWVUTSRQPONMLKJIHGFEDCBA QQQQ BCAB end |
Case 1: 26 Case 2: 1 Case 3: 1 Case 4: 2 |
Bộ 4: chồng thứ nhất từ dưới lên là B, A; chồng thứ hai là C, B. |
Bình luận