XDA - XẾP ĐĨA
Dữ liệu vào: standard input
Dữ liệu ra: standard output
Giới hạn thời gian: 1.0 giây
Giới hạn bộ nhớ: 128 megabyte
Đăng bởi: admin

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à a1, a2, ..., an. Một chiếc đĩa có độ bền ai nghĩa là Nam có thể xếp lên trên đĩa đó tối đa achiế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: Cho tệp văn bản XEPDIA.INP gồm hai dòng:

  • Dòng thứ nhất chứa số nguyên dương n (1<=n<=105 là số lượng đĩa.
  • Dòng thứ hai gồm n số nguyên a1, a2, ..., an với ai  là độ bền của chiếc đĩa thứ i (0<=ai<=109). Các số trên một dòng ghi cách nhau bởi dấu cách. 

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

Ví dụ:

XEPDIA.INP

XEPDIA.OUT

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ụ

Back to Top