| Nộp bài | Các bài nộp | Làm tốt nhất | Về danh sách bài |
PTIT134I - Xếp khối hộp |
Nhà Tèo bán tạp hóa và Tèo thường lấy các thùng hàng trống ra làm đồ chơi. Tèo xếp các khối hộp thành kim tự tháp, và thỏa mãn điều kiện hộp phía trên không được nhô ra phía ngoài của hộp đặt liền dưới. Chẳng hạn, hộp có đáy là 5 x 10 sẽ không thể đặt lên trên hộp có kích thước đáy 4 x 12.
Tèo có n khối hộp và có thể đặt nó theo bất cứ trạng thái nào. Chẳng hạn một hộp có kích thước 5 x 10 x 12 thì có thể chọn đáy là mặt 5 x 10, 10 x 12 hoặc 5 x 12.
Nhiệm vụ của các bạn là hãy xác định xem Tèo có thể sử dụng nhiều nhất bao nhiêu khối hộp cho trò chơi của mình.
Ví dụ ở test 1, có 4 chiếc hộp, nhưng Tèo chỉ có thể sử dụng nhiều nhất 3 chiếc hộp.
Thứ tự các hộp (theo thứ tự từ dưới đáy lên) là hộp 3, 1, 4 hoặc 2, 1, 4.
Input
Gồm nhiều test.
Mỗi test gồm 1 số n (<= 10) là số lượng hộp mà Tèo đang có.
n dòng tiếp theo, dòng thứ i gồm 3 số nguyên dương mô tả 3 chiều của chiếc hộp thứ i.
Input kết thúc bởi số 0.
Output
Với mỗi test, in ra số lượng khối hộp lớn nhất mà Tèo có thể sử dụng.
Example
Input:
4
2 2 9
6 5 5
1 4 9
3 1 1
3
2 4 2
1 5 2
3 4 1
0
Output:
Case 1: 3
Case 2: 3
| Được gửi lên bởi: | adm |
| Ngày: | 2013-02-28 |
| Thời gian chạy: | 1s-10s |
| Giới hạn mã nguồn: | 50000B |
| Memory limit: | 1536MB |
| Cluster: | Cube (Intel G860) |
| Ngôn ngữ cho phép: | ASM32-GCC ASM32 MAWK BC C CSHARP C++ 4.3.2 CPP CPP14 COFFEE LISP sbcl DART FORTH GO JAVA JS-RHINO JS-MONKEY KTLN OCT PAS-GPC PAS-FPC PERL PERL6 PROLOG PYTHON PYTHON3 PY_NBC R RACKET SQLITE SWIFT UNLAMBDA |
