trang chủ / đề bài / 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

  • 1≤n≤2·105
  • 1≤ai≤2·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.47 awk 1.3.4 gcc 16.2.0 dotnet 10.0.402 g++ 16.2.0 g++-themis 16.2.0 g++17 16.2.0 g++20 16.2.0 g++23 16.2.0 clang++ 22.1.8 dmd 2.113.0 dart 3.13.6 gforth 0.7.3 gfortran 15.3.0 go 1.27.3 groovyc 5.1.3 javac 26.0.2.1 node 26.12.1 julia 1.13.2 kotlinc 2.4.21 lean 4.35.0 sbcl 2.2.9 lua 5.5.1 nim 2.2.12 fpc 3.2.2 fpc-themis 3.2.2 perl 5.42.3 php 8.5.12 pike 8.0 swipl 9.0.4 pypy3 7.3.23 python3 3.15.1 racket 8.7 ruby 4.0.8 rustc 1.99.1 csc 5.3.0 ctoj-scratch 0.0.1 sed 4.9 swiftc 6.4.1 tclsh 8.6 bun 1.4.4 deno 2.9.8 v 0.5.2 zig 0.17.0