trang chủ / bài tập / polytrain

Polycarp luyện tập

Đề bài

Mô tả

Polycarp muốn luyện tập trước một kỳ thi lập trình. Trong ngày huấn luyện thứ nhất anh phải giải đúng 1 bài, ngày thứ hai đúng 2 bài, ngày thứ ba đúng 3 bài, và cứ như vậy: trong ngày thứ k anh phải giải đúng k bài.

Polycarp có một danh sách n bộ đề, bộ đề thứ i gồm ai bài. Mỗi ngày anh chọn đúng một bộ đề chưa dùng và giải nó. Anh giải đúng k bài từ bộ đề đó (những bài còn lại của bộ đề bị bỏ đi). Nếu tại ngày thứ k không còn bộ đề nào chưa dùng có ít nhất k bài, Polycarp dừng luyện tập.

Hỏi Polycarp có thể luyện tập được nhiều nhất bao nhiêu ngày nếu chọn các bộ đề một cách tối ưu?

Dữ liệu vào

  • Dòng đầu chứa số nguyên n là số bộ đề.
  • Dòng thứ hai chứa n số nguyên a1,a2,,an là số bài của từng bộ đề.

Dữ liệu ra

In ra một số nguyên: số ngày nhiều nhất Polycarp có thể luyện tập.

Ràng buộc

  • 1n2·105
  • 1ai2·105

Ví dụ

Input Output Giải thích
4
3 1 4 1
3 Ngày 1 dùng bộ có 1 bài, ngày 2 dùng bộ có 3 bài, ngày 3 dùng bộ có 4 bài. Không còn bộ nào 4 bài nên dừng sau 3 ngày.
3
1 1 1
1 Chỉ có thể luyện ngày đầu (giải 1 bài); không bộ nào có 2 bài.
5
1 1 1 2 2
2 Ngày 1 dùng bộ 1 bài, ngày 2 dùng bộ 2 bài; không bộ nào còn lại có 3 bài.

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