Skip to content
Narrow screen resolution Wide screen resolution Auto adjust screen size Increase font size Decrease font size Default font size default color grey color
         
 | 
VNOI - Olympic tin học Việt Nam

Điểm tin VOJ

Số thành viên:6040
Số bài tập:1001
Số bài nộp:722923
Bài nộp hôm nay:0

Top 10 thành viên xuất sắc

HạngThành viênĐiểm
1mr_invincible587.9
2white_cobra418.6
3hieult403.4
4phaleq384.0
5vodanh9x368.2
6con_nha_ngheo352.0
7flash_mt350.2
8darksabers349.8
9yenthanh132345.3
10rockman9x_94343.1
Diễn đàn arrow Thư viện arrow Đề thi arrow VOI (thi quốc gia) arrow 2007 arrow 1. Dãy con không giảm dài nhất
1. Dãy con không giảm dài nhất In E-mail
(16 votes)
Người viết: Ngô Minh Đức   
20/06/2008

Bài 1. Dãy con không giảm dài nhất  (6 điểm)

Cho dãy số nguyên dương a1, a2, ..., an.

Dãy số

ai, ai+1, ..., aj thỏa mãn ai ≤ ai+1 ≤ ... ≤ aj,

với 1 ≤ ij n được gọi là dãy con không giảm của dãy số đã cho và khi đó số j-i+1 được gọi là độ dài của dãy con này.

Yêu cầu: Trong số các dãy con không giảm của dãy số đã cho mà các phần tử của nó đều thuộc dãy số {uk} xác định bởi u1 = 1, uk = uk-1 + k (k ≥ 2), hãy tìm dãy con có độ dài lớn nhất.

Dữ liệu: Vào từ file văn bản MAXISEQ.INP

·         Dòng đầu tiên chứa một số nguyên dương n (n ≤ 104);

·         Dòng thứ i trong n dòng tiếp theo chứa một số nguyên dương ai (ai ≤ 108) là số hạng thứ i của dãy số đã cho, i = 1, 2, ..., n.

Kết quả: Ghi ra file văn bản MAXISEQ.OUT số nguyên d là độ dài của dãy con không giảm tìm được (quy ước rằng nếu không có dãy con nào thỏa mãn điều kiện đặt ra thì d = 0).

Ví dụ: Cho dãy số có 8 phần tử: 2, 2007, 6, 6, 15, 16, 3, 21. Các dãy con không giảm của dãy số đã cho mà các phần tử của nó đều thuộc dãy {uk} là: 6, 6, 15 và 3, 21 (vì u2 = 3, u3 = 6,     u5 = 15, u6 = 21). Dãy cần tìm là 6, 6, 15 có độ dài là 3.

 

MAXISEQ.INP

MAXISEQ.OUT

8

2

2007

6

6

15

16

3

21

3

 
Tiếp >