SỞ GIÁO DỤC VÀ ĐÀO TẠO HÀ NỘI
CỤM TRƯỜNG THPT
BA ĐÌNH – TÂY HỒ
ĐỀ THI OLYMPIC NĂM HỌC 2011 - 2012
Môn Tin học – Lớp 11
Ngày thi: 14/03/2012
Thời gian làm bài 150 phút, không kể thời gian giao đề.
Đề thi gồm có 02 trang.
Tổng quan đề thi:
STT Tên bài
Tên file
chương
trình
Tên file
dữ liệu
vào
Tên file
Kết quả ra
Điểm
Thời
gian
Bài 1
Tổng các số nguyên tố
Bai1.pas Bai1.inp Bai1.out 6 2 giây
Bài 2
Tổng trong hệ bát phân
Bai2.pas Bai2.inp Bai2.out 5 2 giây
Bài 3
Đoạn được phủ dài nhất
Bai3.pas Bai3.inp Bai3.out 5 2 giây
Bài 4 Đường đi ngắn nhất Bai4.pas Bai4.inp Bai4.out 4 2 giây

Bài 3: Đoạn được phủ dài nhất
Cho N đoạn thẳng có các đầu mút đánh dấu trên trục số là [Li,Ri], i=1 N (Li,Ri có giá trị tuyệt đối
nhỏ hơn 32.000). Viết chương trình tìm đoạn trục số được phủ liên tiếp dài nhất bởi các đoạn thẳng đã
cho?
1
ĐỀ CHÍNH THỨC
Dữ liệu vào trong file văn bản “Bai3.inp” có dạng:
- Dòng đầu là số N (1<N<=5.000)
- N dòng tiếp theo mỗi dòng biểu diễn đầu mút các đoạn thẳng là Li và Ri (mỗi số cách
nhau một dấu cách).
Kết quả cho ra file văn bản “Bai3.out” có dạng:
Một dòng duy nhất ghi độ dài liên tiếp lớn nhất trên trục số mà các đoạn thẳng đã phủ được.
Ví dụ:
Bai3.inp Bai3.out
7
7 12
0 5
20 25
33 38
6 8
27 34
11 19
13
(Có 50% số test có N<100 và |Li|,|Ri| <= 1.000)
Bài 4: Đường đi ngắn nhất
Trong hệ toạ độ vuông góc biểu diễn toạ độ của N hòn đảo là N
1
(X
1
,Y

- Dòng đầu chứa số N, M (2<N<=1.000, 1<M<=100.000)
- Dòng thứ hai là số N
i
và N
j
- N dòng tiếp theo là toạ độ lần lượt của N hòn đảo.
(mỗi số cách nhau một dấu cách)
Kết quả cho ra file văn bản “Bai4.out” có dạng:
- Dòng đầu là số hiệu các đảo nằm trên đường đi ngắn nhất có thể từ đảo N
i
đến N
j
bỏ qua
những đảo không dừng lại đổ xăng mà nằm trên đường đi.
- Dòng thứ hai là độ dài đường đi làm tròn 3 chữ số sau dấu chấm thập phân.
- Nếu không có đường đi nào thỏa mãn ghi số 0.
Ví dụ:
Bai4.inp Bai4.out Hình minh họa
10 5
1 6
0 0
0 10
10 0
5 5
0 5
7 7
4 4
3 3
0 4
6 0