Trò chơi

Xem PDF



Tác giả:
Dạng bài
Điểm: 600 (p) Thời gian: 1.0s Bộ nhớ: 1023M Input: bàn phím Output: màn hình

Trong vòng Gameshow “Tìm kiếm tài năng năm 2019” tại lớp 10 chuyên Tin cho các Đội học sinh tham gia; Trò chơi cho các đội là trò chơi với các con số như sau: cho một số có \(N\) chữ số (gồm \(N\) chữ số viết trong hệ thập phân: \(0, 1, 2, 3, 4, 5, 6, 7, 8, 9\)); tiếp theo: Người dẫn chương trình sẽ tách rời số \(N\) này thành một dãy số gồm \(M\) số bất kỳ theo đúng thứ tự của \(N\) (\(M \leq N\)). Người dẫn chương trình sẽ yêu cầu các đội đưa ra độ dài của dãy con tăng dài nhất từ dãy \(M\) số này;

Ví dụ: Dãy chữ số thập phân \(314159265358979\)

  • Nếu tách dãy trên thành dãy số gồm \(6\) số: \(3, 14, 159, 26, 53, 58979\) thì chúng ta tìm được dãy con tăng dài nhất gồm \(5\) số là: \(3, 14, 26, 53, 58979\).
  • Nhưng nếu tách thành dãy số gồm \(10\) số: \(3, 1, 4, 1, 5, 9, 26, 53, 58, 979\) thì chúng ta sẽ tìm được dãy con tăng dài nhất gồm \(8\) số là: \(3, 4, 5, 9, 26, 53, 58, 979\).

Yêu cầu: Cho dãy \(N\) chữ số thập phân, hỏi với cách chơi như trên thì các Đội sẽ tìm được dãy con tăng dài nhất tối đa là bao nhiêu phần tử?

Input

  • Dòng đầu tiên ghi số nguyên dương \(N\) (\(1\leq N\leq 1000\)).
  • Dòng thứ hai là một xâu gồm \(N\) chữ số thập phân.

Output

  • Một số duy nhất là độ dài của dãy con tăng dài nhất tìm được.

Scoring

  • Subtask \(1\) (\(50\%\) số điểm): \(n \leq 20\).
  • Subtask \(2\) (\(25\%\) số điểm): \(n \leq 200\).

Example

Test 1

Input
15 
314159265358979 
Output
8

Bình luận