Khung cửa
Đề bài
Mô tả
Cho các thanh gỗ bằng nhau, mỗi thanh dài . Cần làm khung cho hai cánh cửa giống nhau, mỗi khung gồm:
- Hai cạnh đứng (trái và phải), mỗi cạnh dài ;
- Một cạnh trên dài .
Như vậy tổng cộng cần đoạn dài và đoạn dài . Mỗi đoạn phải được lấy nguyên vẹn (liền mạch, không nối) từ một thanh gỗ; có thể cắt một thanh gỗ thành nhiều đoạn nhỏ hơn để dùng cho nhiều cạnh, miễn là mỗi cạnh là một đoạn liền.
Hãy tìm số lượng thanh gỗ tối thiểu cần dùng để làm xong khung cho hai cánh cửa.
Dữ liệu vào
- Dòng thứ nhất chứa số nguyên — độ dài mỗi thanh gỗ.
- Dòng thứ hai chứa số nguyên — độ dài cạnh đứng.
- Dòng thứ ba chứa số nguyên — độ dài cạnh trên.
Dữ liệu ra
In ra một số nguyên duy nhất — số lượng thanh gỗ tối thiểu cần dùng.
Ràng buộc
Ví dụ
| Input | Output | Giải thích |
|---|---|---|
| 8 1 2 |
1 | Tổng độ dài đoạn là , vừa đúng một thanh gỗ. |
| 5 3 4 |
6 | Không đoạn nào ghép cặp được trong cùng một thanh dài , nên mỗi đoạn chiếm một thanh. |
| 6 4 2 |
4 | Một cách tối ưu: hai thanh chứa , hai thanh chứa thừa — tổng thanh. |
| 20 5 6 |
2 | Một thanh chứa hai đoạn và một đoạn (); thanh còn lại chứa hai đoạn và một đoạn . |
Bình luận