Hai con dấu
Đề bài
Mô tả
Cho một tờ giấy hình chữ nhật kích thước và con dấu. Con dấu thứ để lại một vết mực hình chữ nhật kích thước .
Bạn phải chọn ra hai con dấu khác nhau và đóng mỗi con dấu đúng một lần lên tờ giấy. Mỗi vết dấu phải nằm trọn trong tờ giấy, có các cạnh song song với cạnh tờ giấy, và trước khi đóng bạn được phép xoay con dấu (vết trở thành ). Hai vết dấu không được chồng lên nhau, nhưng được phép chạm cạnh nhau.
Lưu ý rằng việc từng con dấu riêng lẻ vừa tờ giấy là chưa đủ: hai vết dấu còn phải cùng nằm trên tờ giấy mà không đè lên nhau.
Hãy tìm tổng diện tích lớn nhất mà hai vết dấu có thể chiếm. Nếu không tồn tại cặp con dấu nào thỏa mãn, in ra .
Dữ liệu vào
- Dòng đầu chứa ba số nguyên , , () — số con dấu và kích thước tờ giấy.
- dòng tiếp theo, dòng thứ chứa hai số nguyên , () — kích thước vết của con dấu thứ .
Dữ liệu ra
In ra một số nguyên duy nhất — tổng diện tích lớn nhất mà hai vết dấu có thể chiếm, hoặc nếu không chọn được hai con dấu nào.
Ràng buộc
- Hai con dấu được chọn phải khác nhau (khác chỉ số), kể cả khi chúng có cùng kích thước.
Ví dụ
| Input | Output | Giải thích |
|---|---|---|
| 2 2 2 1 2 2 1 |
4 | Xoay con dấu thứ hai để nó cũng thành , rồi đặt hai vết cạnh nhau theo chiều ngang. Chúng phủ kín tờ giấy , tổng diện tích . |
| 4 10 9 2 3 1 1 5 10 9 11 |
56 | Con dấu thứ tư không vừa tờ giấy dù xoay kiểu nào ( và ). Chọn con dấu thứ ba xoay thành (diện tích ) và con dấu thứ nhất xoay thành (diện tích ), xếp chồng theo chiều dọc: chiều cao . Tổng . |
| 3 10 10 6 6 7 7 20 5 |
0 | Con dấu không vừa tờ giấy. Hai con dấu còn lại và mỗi cái đều vừa tờ giấy, nhưng không thể đặt đồng thời vì theo cả chiều ngang lẫn chiều dọc. |
Bình luận