Jerry và thạch
Đề bài
Mô tả
Sinh nhật lần thứ của Jerry sắp đến! Cũng như mọi chú chuột khác, tuổi là một cột mốc rất quan trọng trong đời Jerry. Nhân dịp này, Jerry mời rất nhiều bạn bè đến nhà dự một bữa tiệc thật đặc biệt. Đợi Tom ngủ say, Jerry lặng lẽ lẻn vào tủ lạnh và tìm thấy một miếng thạch sương sáo rất to! Jerry lặng lẽ mang miếng thạch đi và... đến giờ vui vẻ rồi!
Miếng thạch Jerry lấy được là một hình hộp chữ nhật có ba kích thước lần lượt là , và . Jerry muốn chia nó thành nhiều miếng nhỏ hơn bằng một số nhát cắt. Để các miếng thạch trông thật ngon mắt, mỗi nhát cắt của Jerry phải chia một miếng nào đó thành đúng hai miếng nhỏ hơn, cả hai đều là hình hộp chữ nhật có các kích thước nguyên. Ngoài ra, nhát cắt phải song song với ít nhất một mặt của miếng đang bị cắt.
Sau khi cắt xong, Jerry đặt các miếng thạch lên đĩa. Khi đặt một miếng, Jerry luôn xoay nó sao cho mặt lớn nhất nằm trên đĩa. Cụ thể, nếu các kích thước của một miếng là , và với thì diện tích mặt đáy của nó luôn là và chiều cao luôn bằng .
Jerry chỉ coi một miếng thạch là dễ thương khi chiều cao của nó ít nhất là . Jerry chỉ đặt các miếng dễ thương lên đĩa và vứt bỏ mọi miếng không dễ thương. Để có một đĩa thạch thật đẹp, Jerry muốn tổng diện tích mặt đáy của các miếng thạch trên đĩa lớn nhất có thể.
Trước khi cắt miếng thạch ngon lành của mình, Jerry muốn biết giá trị lớn nhất của tổng diện tích mặt đáy của tất cả các miếng thạch dễ thương trên đĩa. Jerry rất giỏi trốn, chạy và trộm đồ, nhưng lại không giỏi lập trình. Hãy giúp Jerry!
Dữ liệu vào
- Dòng đầu tiên chứa một số nguyên () là số bộ dữ liệu.
- Mỗi dòng trong dòng tiếp theo mô tả một bộ dữ liệu gồm số nguyên dương , , và (), trong đó , , là các kích thước của miếng thạch Jerry lấy được và là chiều cao nhỏ nhất của một miếng thạch dễ thương.
Dữ liệu ra
Với mỗi bộ dữ liệu, in ra trên một dòng một số nguyên là giá trị lớn nhất có thể của tổng diện tích mặt đáy của các miếng thạch trên đĩa.
Ràng buộc
- .
- .
Ví dụ
| Input | Output | Giải thích |
|---|---|---|
| 2 5 4 3 2 4 3 2 1 |
30 24 |
Bộ thứ nhất: cắt miếng thành hai miếng và đặt cả hai lên đĩa; mỗi miếng có diện tích đáy và chiều cao , tổng là . Bộ thứ hai: mọi miếng đều có chiều cao ít nhất nên luôn dễ thương; cắt miếng thành khối lập phương cạnh , mỗi khối có diện tích đáy . |
| 3 5 5 3 2 3 3 3 4 6 5 4 1 |
33 0 120 |
Bộ thứ nhất: cắt thành (diện tích đáy ) và , rồi cắt miếng sau thành và (mỗi miếng ): tổng , nhiều hơn mọi cách chỉ cắt thành các lát song song. Bộ thứ hai: không miếng nào cao được tới . Bộ thứ ba: với , cắt thành khối lập phương cạnh . |
Bình luận