//
you're reading...
00 - Chủ đề chung, Đề thi cấp tỉnh - Đồng Tháp

Bài tập huấn luyện: Nối khoảng

[Bộ đề huấn luyện vòng tỉnh Đồng Tháp]


Chọn đội tuyển dự thi quốc gia – 2017 – Ngày thi 21/6/2016 – Bài 2


Đề bài


Cho n khoảng đóng trên trục số đánh số từ 1 tới n, khoảng thứ i là [ai,bi]. Hãy tìm một dãy dài nhất gồm các khoảng đóng nối nhau lấy từ n khoảng đóng đã cho.

Một dãy khoảng đóng gọi là nối nhau nếu điểm cuối của khoảng đứng liền trước trùng với điểm đầu của khoảng đứng liền sau xét trong dãy khoảng đóng. Ví dụ [1,3]; [3,4]; [4,5] là một dãy khoảng đóng nối nhau.

Dữ liệu: Vào từ file văn bản CONINT.INP có cấu trúc như sau:

  • Dòng thứ nhất chứa số nguyên dương n (n ≤ 105)
  • n dòng tiếp theo, dòng thứ i chứa hai số nguyên ai, bi (-105 ai <bi ≤105; i=1..n)

Kết quả: Ghi ra file văn bản CONINT.OUT một số nguyên duy nhất là số khoảng nối nhau liên tiếp dài nhất.

Ví dụ:

CONINT.INP CONINT.OUT
5

4 5

2 7

1 3

7 9

3 4

3 Giải thích: 3 đoạn nối nhau là

[1,3]; [3,4]; [4,5]

 

Chú ý:

25% số điểm ứng với các test có n ≤ 10

50% số điểm ứng với các test có n ≤ 1000

 


Hướng dẫn


[]


Chương trình


[]

Advertisements

About pascalteacher

Trang thông tin Toán học và Tin học

Thảo luận

Không có bình luận

Trả lời

Mời bạn điền thông tin vào ô dưới đây hoặc kích vào một biểu tượng để đăng nhập:

WordPress.com Logo

Bạn đang bình luận bằng tài khoản WordPress.com Đăng xuất / Thay đổi )

Twitter picture

Bạn đang bình luận bằng tài khoản Twitter Đăng xuất / Thay đổi )

Facebook photo

Bạn đang bình luận bằng tài khoản Facebook Đăng xuất / Thay đổi )

Google+ photo

Bạn đang bình luận bằng tài khoản Google+ Đăng xuất / Thay đổi )

Connecting to %s

Các tác giả

Categories

Tháng Mười Hai 2016
H B T N S B C
« Th11   Th1 »
 1234
567891011
12131415161718
19202122232425
262728293031  

NCT Computer

Flickr Photos

Thống kê

  • 149,868 lượt xem

pascalteacher.nct@gmail.com


Trang huấn luyện học sinh giỏi Tin học

%d bloggers like this: