trang chủ / đề bài / icpcwf07_b

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ừ 1 đến 1000 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ừ 1) 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 1 đến 1000 chữ cái in hoa A..Z.
  • Mỗi file có không quá 100 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 4 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

Không có bình luận tại thời điểm này.

gnatmake 12.2.0 a68g 3.1.2 nasm 2.16.1 as_x64 2.47 awk 1.3.4 gcc 16.2.0 dotnet 10.0.402 g++ 16.2.0 g++-themis 16.2.0 g++17 16.2.0 g++20 16.2.0 g++23 16.2.0 clang++ 22.1.8 dmd 2.113.0 dart 3.13.6 gforth 0.7.3 gfortran 15.3.0 go 1.27.3 groovyc 5.1.3 javac 26.0.2.1 node 26.12.1 julia 1.13.2 kotlinc 2.4.21 lean 4.35.0 sbcl 2.2.9 lua 5.5.1 nim 2.2.12 fpc 3.2.2 fpc-themis 3.2.2 perl 5.42.3 php 8.5.12 pike 8.0 swipl 9.0.4 pypy3 7.3.23 python3 3.15.1 racket 8.7 ruby 4.0.8 rustc 1.99.1 csc 5.3.0 ctoj-scratch 0.0.1 sed 4.9 swiftc 6.4.1 tclsh 8.6 bun 1.4.4 deno 2.9.8 v 0.5.2 zig 0.17.0