Chồng Hộp
Đề bài
Mô tả
Có chiếc hộp, tất cả cùng kích thước. Hộp thứ có độ bền , nghĩa là có thể chịu được tối đa chiếc hộp khác nằm phía trên nó.
Vì các hộp cùng kích thước nên trên đỉnh mỗi chiếc hộp chỉ có thể đặt trực tiếp đúng một chiếc hộp khác. Một chồng hộp được tạo thành bằng cách xếp các hộp chồng lên nhau theo một thứ tự, sao cho với mỗi hộp trong chồng, số hộp nằm phía trên nó không vượt quá .
Hãy chia tất cả chiếc hộp vào các chồng (mỗi hộp thuộc đúng một chồng) sao cho số chồng là ít nhất có thể, và in ra số chồng tối thiểu đó.
Dữ liệu vào
- Dòng đầu chứa số nguyên .
- Dòng thứ hai chứa số nguyên .
Dữ liệu ra
- Một số nguyên duy nhất — số chồng hộp ít nhất cần dùng.
Ràng buộc
Ví dụ
| Input | Output | Giải thích |
|---|---|---|
| 3 0 0 10 |
2 | Hộp 1 và hộp 2 đều không chịu được hộp nào ở trên, nên ta xếp: chồng 1 gồm hộp 2 (trên) và hộp 3 (dưới); chồng 2 gồm hộp 1 đứng một mình. |
| 5 0 1 2 3 4 |
1 | Xếp các hộp theo thứ tự từ trên xuống: 1, 2, 3, 4, 5. Hộp dưới cùng có độ bền và đỡ đúng hộp ở trên. |
| 4 0 0 0 0 |
4 | Không hộp nào chịu được hộp khác, nên mỗi hộp phải đứng một mình. |
| 9 0 1 0 2 0 1 1 2 10 |
3 | Có thể chia thành 3 chồng, ví dụ một chồng chứa hộp độ bền ở đáy với ba hộp nhỏ chất lên. |
Bình luận