XẾP ĐĨA

Khách sạn XYZ là nơi đón tiếp các đoàn thể thao về nghỉ ngơi trong SEA Games 31. Sau mỗi bữa ăn, khách sạn sẽ phải rửa dọn rất nhiều chiếc đĩa. Nam là người chịu trách nhiệm rửa sạch và xếp chúng lên nhau. Nam có \(n\) chiếc đĩa được đánh số từ \(1\) tới \(n\). Những chiếc đĩa có độ bền lần lượt là \(a_{1},a_{2},\ldots,\ a_{n}.\) Một chiếc đĩa có độ bền \(a_{i}\) nghĩa là Nam có thể xếp lên trên đĩa đó tối đa \(a_{i}\) chiếc đĩa khác, nếu xếp lên nhiều hơn thì đĩa đó sẽ bị vỡ.

Yêu cầu: Hãy cho biết số đĩa tối đa mà Nam có thể xếp được sao cho đĩa không bị vỡ.

Dữ liệu vào:

+ Dòng thứ nhất chứa số nguyên dương \(n\ (1 \leq n \leq 10^{5})\) là số lượng đĩa.

+ Dòng thứ hai gồm\(\ n\) số nguyên \(a_{1},a_{2},\ldots,\ a_{n}\ \)với \(a_{i}\) là độ bền của chiếc đĩa thứ \(i\) \((0 \leq a_{i} \leq 10^{9};\ 1 \leq i \leq n)\). Các số trên một dòng ghi cách nhau bởi dấu cách.

Kết quả: Ghi một số nguyên duy nhất là đáp án của bài toán.

Ví dụ 1:

Input Output
3
1 2 1
3

Giải thích: Chồng đĩa cao nhất được xếp với 3 đĩa theo thứ tự từ dưới lên trên là đĩa thứ 2, đĩa thứ 1 rồi đến đĩa thứ 3.

Ví dụ 2:

Input Output
6
0 0 0 0 0 0
1

Giải thích: Không có chiếc đĩa nào được phép đặt đĩa khác lên nên mỗi đĩa phải đặt riêng 1 chồng, vì vậy số đĩa tối đa có thể xếp là 1.

Giới hạn: 60% test có \(n \leq 10^{3}\)

40% test có \(n \leq 10^{5}\)

Bạn cần đăng nhập để nộp bài

hpcode.edu.vn
Code tích cực
Trong 24h
  1. trungnam (6/7)
  2. sythai (5/8)
  3. npk1605 (5/10)
Trong 7 ngày
  1. nguyenanhvu (40/64)
  2. khieuquan (35/59)
  3. ngokhang (27/55)
Trong 30 ngày
  1. quechi (85/105)
  2. dangphong3108 (79/125)
  3. kiennhientv (79/179)
Thống kê
AC/Sub: 97887/180710
Pascal: 17121
C++: 130348
Python: 33199
Lượt xem/tải tests: 38905

Lưu Hải Phong - 2020
[email protected]