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
Empodia In E-mail
(3 votes)
Người viết: Ngô Minh Đức   
10/04/2008
Bài Empodia
Nhà triết học, toán học cổ xưa Pythagoras đã tin rằng bản chất tự nhiên của thực tế là toán học. Ngày nay các nhà sinh vật học nghiên cứu tính chất của dãy sinh. Một dãy sinh là một dãy gồm M số nguyên được cho như sau:

- Bao gồm các số 0,1,…M -1.
- Bắt đầu là số 0 và kết thúc là số M -1, và
- Không có hai phân từ E, E+1 đứng liền kề trong thứ tự này.
Một dãy con bao gồm các phần tử liên tiếp trong tập sinh được gọi là một đoạn. Một đoạn của tập sinh được gọi là một khoảng khung nếu như nó chứa tất cả các số nguyên có giá trị nằm trong khoảng từ số đầu tiên (phải là phần tử nhỏ nhất trong đoạn) đến số cuối cùng (phải là phần tử lớn nhất và khác phần từ đầu tiên). Một khoảng khung được gọi là một empodio nếu nó không chứa bất kỳ một khoảng khung nào nhỏ hơn.
Ví dụ:
Chúng ta hãy xem xét một dãy sinh {0,3,5,4,6,2,1,7}. Toàn bộ dãy sinh là một khoảng khung. Tuy nhiên, nó chứa một khoảng khung khác là {3,5,4,6} và vì thế nó không phải là một empodio. Khoảng khung {3,5,4,6} không chứa một khoảng khung nào nhỏ hơn vì thế nó là một empodio. Hơn nữa nó là empodio duy nhất của dãy sinh này.
Cho trước một dãy sinh bạn hãy viết chương trình tìm tất cả các empodio (nhiều nhất có thể).
INPUT
Dữ liệu được cho trong file empodia.in.
- Dòng đầu tiên chứa duy nhất một số nguyên M (1≤M≤60000): là số các số nguyên trong tập sinh.
- M dòng tiếp theo chứa các số nguyên của tập sinh theo thứ tự tuần tự. Mỗi một dòng chứa duy nhất một số nguyên.

OUPUT
Kết quả được lưu trong file empodia.out.
- Dòng đầu tiên chứa một số nguyên H: là số empodio tìm được.
- H dòng tiếp theo mô tả tất cả các empodio theo thứ tự xuất hiện của các phần tử trong dãy sinh. Mỗi một dòng chứa hai số nguyên A và B (theo thứ tự ) được ngăn cách bởi khoảng trắng, ở đó phần tử thứ A trong file input là phần tử đầu tiên của empodio và phần tứ thứ B trong file input là phần tử cuối cùng của empodio.

Ví dụ:

 
empodia.in
8
0
3
5
4
6
2
1
7
empodia.out
1
2 5
 
< Trước   Tiếp >