BABYLON - Tháp babylon
Dữ liệu vào: standard input
Dữ liệu ra: standard output
Giới hạn thời gian: 1.0 giây
Giới hạn bộ nhớ: 128 megabyte
Đăng bởi: admin

Có lẽ bạn đã nghe nói về các truyền thuyết của Tháp babylon. Ngày nay nhiều chi tiết của câu chuyện này bị lãng quên. Vì vậy, chúng tôi sẽ cho bạn biết toàn bộ câu chuyện:

Người Babylon có n loại khối hộp, và mỗi loại có số lượng không giới hạn. Khối hộp thứ i là một hình hộp chữ nhật với kích thước (xi, yi, zi). Một khối có thể được xoay để xác định đáy và chiều cao của hộp. Họ muốn xây tòa tháp cao nhất có thể bằng cách xếp chồng các khối lên nhau. Vấn đề là, trong việc xây dựng một tòa tháp, một khối chỉ có thể được đặt trên khối khác nếu đáy của nó có kích thước nhỏ hơn đáy của khối kia. Chiều cao của tháp Babylon là tổng chiều cao các khối được xếp chồng lên nhau.

Công việc của bạn là viết một chương trình để xác định chiều cao cao nhất của tòa tháp  Babylon có thể xây dựng với một tập hợp các khối.

Dữ liệu vào: Dữ liệu chứa nhiều bộ test khác nhau, mỗi bộ test có dạng như sau:

+ Số đầu tiên chứa giá trị n (1 ≤ n ≤ 30), nếu n = 0 là dấu hiệu kết thúc đầu vào.

+ n dòng tiếp theo, dòng thứ i chứa 3 số xi, yi, zi là kích thước của khối hộp thứ i.

Kết quả ra: Gồm nhiều dòng: mỗi dòng tương ứng với kết quả của mỗi bộ test. Các dòng in ra thông báo như sau: "Case case: maximum height = height"

Ví dụ

  • input
    1
    10 20 30
    2
    6 8 10
    5 5 5
    7
    1 1 1
    2 2 2
    3 3 3
    4 4 4
    5 5 5
    6 6 6
    7 7 7
    5
    31 41 59
    26 53 58
    97 93 23
    84 62 64
    33 83 27
    0
    output
    Case 1: maximum height = 40
    Case 2: maximum height = 21
    Case 3: maximum height = 28
    Case 4: maximum height = 342
Back to Top