Bedao Regular Contest 19 - Dãy bậc thang
Xem dạng PDF
Gửi bài giải
Điểm:
0,30 (OI)
Giới hạn thời gian:
1.0s
Giới hạn bộ nhớ:
256M
Input:
stdin
Output:
stdout
Tác giả:
Dạng bài
Ngôn ngữ cho phép
C, C++, Go, Java, Kotlin, Pascal, PyPy, Python, Rust, Scratch
Cho dãy số gồm ~n~ số nguyên dương ~a_1, a_2, \ldots, a_n~.
Bạn hãy tìm dãy số ~b_1, b_2, \ldots, b_k~ dài nhất thỏa mãn:
~1 \le b_1 < b_2 < \ldots < b_k \le n~.
~a_{b_1} + 1 = a_{b_2} + 2 = \ldots = a_{b_k} + k~.
Input
Dòng đầu tiên gồm một số nguyên dương ~n~ là số lượng phần tử của dãy ~a~ (~1 \le n \le 10^6~).
Dòng thứ hai chứa ~n~ số nguyên dương mô tả dãy ~a_1, a_2, \ldots a_n~. (~1 \le a_i \le 10^6~, ~1 \le i \le n~).
Output
Dòng thứ nhất in ra một số nguyên dương ~k~ là số lượng phần tử của dãy ~b~ dài nhất tìm được.
Dòng thứ hai in ra ~k~ số nguyên dương mô tả dãy ~b_1, b_2, \ldots, b_k~.
Nếu có nhiều dãy ~b~ thỏa mãn thì in ra một dãy bất kì.
Scoring
| Subtask | Điểm | Giới hạn |
|---|---|---|
| 1 | ~30~ | ~n \le 20~ |
| 2 | ~40~ | ~n \le 5000~ |
| 3 | ~20~ | ~n \le 10^5~ |
| 4 | ~10~ | Không có ràng buộc gì thêm |
Sample Input 1
7
5 6 1 4 2 3 2
Sample Output 1
4
1 4 6 7
Bình luận
Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.