SỞ GD&ĐT QUẢNG BÌNH KÌ THI CHỌN HSG TỈNH NĂM HỌC 2014-2015
Khóa thi ngày 17 - 3 - 2015
ĐỀ CHÍNH THỨC Môn: Tin học
LỚP 11 THPT - VÒNG II
Họ và tên: ………………………….. Thời gian: 180 phút (không kể thời gian giao đề)
Số báo danh: ………..……………... Đề gồm có 02 trang

ĐỀ RA
Sử dụng ngôn ngữ lập trình Turbo Pascal để lập trình giải các bài toán sau:
Câu 1: (3,0 điểm) Đoạn rời dài nhất DOANROI.PAS
Trên trục số, cho N đoạn thẳng được đánh số từ 1 đến N. Mỗi đoạn thẳng được xác định bởi giá trị điểm đầu a và giá trị điểm cuối b (aYêu cầu: Hãy chọn tập nhiều nhất các đoạn thẳng sao cho không có hai đoạn thẳng nào đôi một giao nhau (kể cả hai đầu mút).
Dữ liệu vào: Cho trong file văn bản DOANROI.INP có cấu trúc như sau:
- Dòng 1: Ghi số nguyên dương N là số đoạn thẳng (1 <= N <= 1000).
- Dòng thứ i trong N dòng tiếp theo: Ghi 2 số a, b là giá trị điểm đầu và điểm cuối của đoạn thứ i, hai số ghi cách nhau ít nhất một dấu cách (-32000 <= a,b <= 32000).
Dữ liệu ra: Ghi ra file văn bản DOANROI.OUT theo cấu trúc như sau:
- Dòng 1: Ghi số nguyên dương M là số lượng lớn nhất các đoạn thẳng tìm được.
- Dòng 2: Ghi chỉ số của M đoạn thẳng được chọn theo thứ tự tăng dần của tọa độ điểm đầu. (Nếu có nhiều cách chọn chỉ cần ghi một cách)
Ví dụ:
DOANROI.INP
DOANROI.OUT

3
2

3 9
2 1

1 2


5 10



Câu 2: (3,5 điểm) Hoán vị HOANVI.PAS
Cho X là số nguyên dương có N chữ số, các chữ số đôi một khác nhau và số nguyên dương M (1<=N<=9 ;2<=M<=20)
Yêu cầu: Tìm số Y là hoán vị các chữ số của X thỏa mãn:
+ Y>X
+ Y chia hết cho M.
+ Y nhỏ nhất
Dữ liệu vào: Cho trong file văn bản HOANVI.INP có cấu trúc:
- Dòng 1: Ghi 2 số N, M hai số cách nhau ít nhất một dấu cách.
- Dòng 2: Ghi số X
Dữ liệu ra: Ghi ra file văn bản HOANVI.OUT theo cấu trúc.
- Dòng 1: Nếu tồn tại số Y thì ghi Y, Nếu không tồn tại thì ghi 0.
HOANVI.INP
HOANVI.OUT

HOANVI.INP
HOANVI.OUT

3 4 213
312

3 5 213
0

Câu 3: (3,5 điểm) Xây dựng hệ thống đường vượt lũ XAYDUNG.PAS
Để giảm bớt thiệt hại cho người dân vùng lũ Miền Trung, một công ty tư nhân đã tiến hành xây dựng xong các nhà tránh lũ tại N địa điểm có địa hình cao ráo. Các địa điểm được đánh thứ tự từ 1 đến N. Để thuận tiện cho việc đi lại trong mùa mưa lũ, Lãnh đạo công ty đã lập dự án xây dựng các tuyến đường vượt lũ giữa N địa điểm trên. Dự án đã tiến hành khảo sát kinh phí để xây dựng mỗi tuyến đường vượt lũ nối giữa địa điểm i và địa điểm j. Có M tuyến đường đã được khảo sát và khi xây dựng xong thì người dân có thể đi lại được giữa N địa điểm trên trong mùa mưa lũ. Do kinh phí xây dựng còn thiếu nên đến nay dự án chỉ xây dựng xong K tuyến đường trong tổng số M tuyến đường đã khảo sát. Với yêu cầu cấp bách trong mùa mưa lũ năm nay, Lãnh đạo công ty yêu cầu cần xây dựng thêm một số tuyến đường sao cho người dân có thể đi lại được giữa N địa điểm trên và kinh phí xây dựng là ít nhất.
Yêu cầu: Hãy tìm một phương án xây dựng thêm các tuyến đường thỏa mãn yêu cầu của Lãnh đạo công ty.
Dữ liệu vào: Cho trong file văn bản XAYDUNG.INP có cấu trúc:
- Dòng 1: Ghi số 3 nguyên dương N M K, trong đó N là số địa điểm, M là số tuyến đường đã được khảo sát, K là số tuyến đường đã xây dựng xong, (2 ≤ N ≤ 100; N-1 ≤ M ≤
; 0≤K ≤ M).
- M dòng tiếp theo: Mỗi dòng ghi 3 số nguyên dương i j t, trong đó t là kinh phí xây