Chồng Hộp

Đề bài

Mô tả

n chiếc hộp, tất cả cùng kích thước. Hộp thứ i có độ bền xi, nghĩa là có thể chịu được tối đa xi 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 i trong chồng, số hộp nằm phía trên nó không vượt quá xi.

Hãy chia tất cả n 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 n.
  • Dòng thứ hai chứa n số nguyên x1,x2,,xn.

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

  • 1n100
  • 0xi100

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 4 và đỡ đúng 4 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 10 ở đáy với ba hộp nhỏ chất lên.

Bình luận

Không có bình luận tại thời điểm này.

gnatmake 12.2.0 a68g 3.1.2 nasm 2.16.1 as_x64 2.46 awk 1.3.4 gcc 16.1.0 csc 6.12.0.200 g++ 16.1.0 g++-themis 16.1.0 g++17 16.1.0 g++20 16.1.0 g++23 16.1.0 clang++ 22.1.6 dmd 2.112.0 dart 3.12.1 gforth 0.7.3 gfortran 12.2.0 go 1.26.3 groovyc 5.0.6 javac 25.0.3 node 26.2.0 kotlinc 2.3.21 sbcl 2.2.9 lua 5.4.8 nim 2.2.10 fpc 3.2.2 fpc-themis 3.2.2 perl 5.36.0 php 8.5.6 pike 8.0 pypy3 7.3.23 python3 3.14.5 racket 8.7 ruby 4.0.5 rustc 1.96.0 csc 5.3.0 ctoj-scratch 0.0.1 sed 4.9 tclsh 8.6 bun 1.3.14 deno 2.8.1 v 0.5.1 zig 0.16.0