trang chủ / đề bài / icpcwf12_k

Xếp chồng đĩa

Đề bài

Mô tả

Công ty Vận chuyển Đĩa là một nhà bán lẻ trên Internet, đúng như tên gọi, chỉ bán đĩa. Họ tự hào cung cấp bộ sưu tập đĩa ăn phong phú nhất vũ trụ, từ rất nhiều nhà sản xuất. Trong một đợt phân tích chi phí gần đây, công ty phát hiện ra họ tốn rất nhiều tiền cho việc đóng gói đĩa để gửi hàng. Một phần nguyên nhân là các đĩa phải được xếp chồng trước khi cho vào thùng hàng, và việc này có vẻ tốn nhiều thời gian hơn dự kiến. Có lẽ bạn có thể giúp.

Một lô hàng gồm đĩa của nhiều nhà sản xuất. Đĩa của mỗi nhà sản xuất được giao thành một chồng, các đĩa sắp theo kích thước (nhỏ nhất ở trên cùng, lớn nhất ở dưới cùng). Ta gọi một chồng như vậy là chồng đúng thứ tự. Để gửi hàng, bạn phải gộp tất cả đĩa thành một chồng duy nhất, cũng phải đúng thứ tự. Để gộp các chồng của các nhà sản xuất thành một chồng, được phép dùng hai loại thao tác:

  • Tách: một chồng có thể được tách thành hai chồng bằng cách nhấc một phần trên cùng bất kỳ của chồng đó lên và đặt sang một bên thành một chồng mới.
  • Ghép: hai chồng có thể được ghép bằng cách đặt chồng này lên trên chồng kia. Thao tác này chỉ được phép nếu đĩa dưới cùng của chồng ở trên không lớn hơn đĩa trên cùng của chồng ở dưới, nghĩa là chồng sau khi ghép phải đúng thứ tự.

Lưu ý rằng không bao giờ được đặt trực tiếp một phần của một chồng lên trên một chồng khác: phần đó phải được tách ra trước, rồi mới ghép với chồng kia.

Cho một tập các chồng đĩa, hãy tìm số thao tác ít nhất để biến chúng thành một chồng duy nhất. Hình dưới đây ứng với bộ test đầu tiên của ví dụ, cho thấy cách biến hai chồng thành một chồng bằng năm thao tác:

Dữ liệu vào

Dữ liệu vào gồm nhiều bộ test, đọc tới hết file. Mỗi bộ test bắt đầu bằng một dòng chứa số nguyên n (1≤n≤50) là số chồng cần gộp cho một lô hàng. Tiếp theo là n dòng, mỗi dòng mô tả một chồng: dòng bắt đầu bằng số nguyên h (1≤h≤50) là chiều cao của chồng, theo sau là h số nguyên dương cho biết đường kính các đĩa, từ trên xuống dưới. Mọi đường kính không vượt quá 10000. Các số này được cho theo thứ tự không giảm.

Dữ liệu ra

Với mỗi bộ test, in ra số thứ tự của bộ test và số thao tác ít nhất (gồm cả tách và ghép) cần thực hiện để gộp các chồng đã cho thành một chồng duy nhất, theo định dạng trong ví dụ.

Ràng buộc

  • 1≤n≤50, 1≤h≤50.
  • Đường kính các đĩa là số nguyên trong đoạn [1,10000], không giảm từ trên xuống dưới trong mỗi chồng.

Ví dụ

Input Output Giải thích
2
3 1 2 4
2 3 5
3
4 1 1 1 1
4 1 1 1 1
4 1 1 1 1
Case 1: 5
Case 2: 2
Bộ 1 (như hình): tách đĩa 3 khỏi chồng thứ hai, tách cặp đĩa 1,2 khỏi chồng thứ nhất, ghép đĩa 4 lên đĩa 5, ghép đĩa 3 lên chồng 4,5, rồi ghép cặp 1,2 lên trên cùng: 5 thao tác. Bộ 2: mọi đĩa cùng kích thước, chỉ cần ghép ba chồng bằng 2 thao tác.
2
2 1 3
2 2 4
Case 1: 5 Thứ tự cuối cùng phải là 1,2,3,4 và các đĩa này luân phiên thuộc hai chồng, nên phải tách chồng thứ nhất (1∣3) và chồng thứ hai (2∣4) rồi ghép 4 phần lại bằng 3 thao tác: tổng 5.

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