Đề thi chọn đội tuyển chính thức học sinh giỏi dự thi quốc gia THPT môn Tin học - Năm học 2020-2021 - Sở GD&ĐT Ninh Bình (Có đáp án)

SỞ GD&ĐT NINH BÌNH
ĐỀ THI CHÍNH THỨC
ĐỀ THI CHỌN ĐỘI TUYỂN CHÍNH THỨC
 THAM DỰ KỲ THI HỌC SINH GIỎI QUỐC GIA 
Năm học 2020-2021
MÔN: TIN HỌC
Ngày thi 28/10/2020
(Thời gian làm bài 180 phút, không kể thời gian giao đề)
Đề thi gồm 03 câu, trong 03 trang
Họ và tên thí sinh :........................................................Số báo danh:................................
Họ và tên, chữ ký: Cán bộ coi thi số 1:..............................................................................
	 Cán bộ coi thi số 2:.................................................................................
Tổng quan về các bài thi trong đề
TT
Tên bài
File Chương trình
File dữ liệu
File kết quả
Điểm
1
Khu vườn 
COUNTRY. *
COUNTRY. INP
COUNTRY. OUT
6
2
Truyền tin
MESS. *
MESS. INP
MESS. OUT
7
3
Đò ngang
TRANS. *
TRANS. INP
TRANS. OUT
7
Phần mở rộng của File chương trình là PAS hoặc CPP tùy theo ngôn ngữ lập trình sử dụng là Pascal hoặc C++
Cấu hình dịch: G++ 4. 9. 2: -std=c++11 -O2 -s -static -Wl,--stack,
66060288 -lm -x c++ 
Viết chương trình giải các bài toán sau:
Câu 1 (6,0 điểm): Khu vườn
Khu vườn nhà Huy là một dải đất dài hình chữ nhật, được chia thành n vùng, các vùng được đánh số thứ tự từ 1 đến n từ trái qua phải, vùng đất thứ i có chiều cao là ai. Huy quyết định lắp đặt hệ thống tưới nước cho khu vườn của mình. Nước ở một vùng phía trước có thể chảy sang các vùng đất thấp hơn nó ở phía sau. Vùng đất thứ i và vùng đất thứ j chỉ được lắp đặt đường ống nước nối với nhau nếu thỏa mãn 2 điều kiện: i aj.
Yêu cầu: Hãy tính giúp Huy số lượng đường ống cần lắp đặt. 
Dữ liệu: Vào từ tệp văn bản COUNTRY. INP
Dòng đầu ghi số nguyên dương n (1 ≤ n ≤ 100000). 
 Dòng thứ hai gồm n số nguyên dương mỗi số cách nhau bởi một khoảng trắng thể hiện độ cao của n vùng trong khu vườn theo thứ tự từ trái qua phải. Các giá trị độ cao trong đoạn [1, 100000]. 
Kết quả: Ghi ra file văn bản COUNTRY. OUT một số nguyên là số lượng đường ống cần lắp đặt.
Ví dụ:
COUNTRY. INP
COUNTRY. OUT
5
1 2 1 2 1
3
Giải thích:
Có 3 đường ống được lắp đặt, cụ thể là:
- 01 Đường ống nối giữa vùng đất thứ 2 và vùng đất thứ 3. 
- 01 Đường ống nối giữa vùng đất thứ 2 và vùng đất thứ 5.
- 01 Đường ống nối giữa vùng đất thứ 4 và vùng đất thứ 5. 
Ràng buộc: 
Có 50% số test của bài có n≤5000.
50% số test còn lại của bài không có ràng buộc bổ sung.
Câu 2 (7,0 điểm): Truyền tin
Trên Mặt Trăng, công ty Bitland đã thành lập n trạm nghiên cứu. Để đơn giản có thể hình dung mỗi trạm là một điểm (x,y) trên mặt phẳng tọa độ hai chiều. Công ty muốn trang bị cho mỗi trạm nghiên cứu một máy thu phát sóng để có thể trao đổi thông tin giữa hai trạm (trực tiếp hoặc thông qua các trạm trung gian). Để đồng bộ hóa tất cả các máy thu phát sóng ở các trạm nghiên cứu phải giống nhau. 
Trên thị trường, nếu bỏ ra X USD thì sẽ mua được máy thu phát sóng có thể truyền tin trực tiếp giữa hai trạm nếu như khoảng cách giữa hai trạm này không vượt quá X (hay bình phương khoảng cách không vượt quá X). 
Hãy xác định số nguyên X nhỏ nhất sao cho nếu ban Giám đốc quyết định chọn loại máy thu phát sóng có giá X USD để lắp cho mỗi trạm một máy thu phát sóng thì có thể thực hiện việc truyền tin giữa hai trạm bất kỳ (trực tiếp hoặc qua các trạm trung gian). 
Dữ liệu: Vào từ file văn bản MESS. INP
Dòng 1: Chứa số nguyên dương n≤1000.
n dòng tiếp theo, mỗi dòng chứa hai số nguyên x, y cách nhau bởi một khoảng trắng là tọa độ của một trạm nghiên cứu (là các số nguyên nằm trong đoạn [0, 25000]).
Kết quả: Ghi ra file văn bản MESS.OUT một số nguyên là giá trị X nhỏ nhất tìm được. 
Ví dụ:
MESS.INP
MESS.OUT
4
1 3
5 4
7 2
6 1
17
Ràng buộc: 
Có 50% số test của bài có n≤100.
50% số test còn lại của bài không có ràng buộc bổ sung.
Câu 3 (7,0 điểm): Đò ngang
Ở dọc hai bên bờ con sông chảy qua thành phố đều có những điểm có thể sử dụng làm bến đỗ cho những con đò ngang. Bên bờ trái có n điểm như vậy đánh số 1, 2,. . . ,n và bên bờ phải có m điểm cũng được đánh số 1, 2,. . . , m. (Việc đánh số được thực hiện trên cả hai bờ tính từ thượng nguồn).
Do chưa có qui hoạch nên hiện tại xuất hiện k tuyến đò ngang, tuyến thứ i nối giữa hai bến hi bên bờ trái với bến wi bên bờ phải, vì thế xuất hiện tình trạng các tuyến đò vắt chéo nhau qua sông (hai tuyến đò gọi là vắt chéo nhau nếu hành trình của chúng cắt nhau). Chính quyền thành phố qui hoạch lại các tuyến đò ngang bằng cách giữ lại một số tuyến đò hiện có theo nguyên tắc:
Mỗi bến bên bờ trái và phải chỉ có nhiều nhất 1 tuyến đò xuất phát từ đó. 
Hai tuyến đò không được chéo nhau. 
Hãy tính số lượng các cách khác nhau để qui hoạch lại các tuyến đò theo nguyên tắc trên. Hai cách được gọi là khác nhau nếu như có ít nhất một tuyến đò xuất hiện trong cách này nhưng không xuất hiện trong cách kia. 
Dữ liệu: Vào từ file văn bản TRANS. INP
Dòng 1 ghi 4 số nguyên dương n, m, k và r lần lượt là số bến ở bờ trái, số bên ở bờ phải, số tuyến đò hiện có và số modun r. 
(1≤n,m≤2×105;1≤k≤106;2≤r≤109)
Dòng thứ i trong k dòng tiếp theo, mỗi dòng mô tả một tuyến đò hiện có gồm hai số nguyên hi và wi (1≤hi≤n;1≤wi≤m).
Kết quả: Ghi ra file văn bản TRANS.OUT một số nguyên duy nhất là số cách khác nhau qui hoạch lại các tuyến đò. Do con số này có thể rất lớn nên chỉ cần in ra phần dư của nó khi chia cho r. 
Các số liên tiếp trên cùng một dòng của file dữ liệu và file kết quả được cách nhau bằng khoảng trắng. 
Ví dụ:
TRANS.INP
TRANS.OUT
3 3 5 100
1 2
2 3
3 1
2 1
3 2
8
Giải thích:
Có 1 cách là không giữ lại tuyến đò nào.
Có 5 cách chỉ giữ lại một tuyến đò.
Có 2 cách chỉ giữ lại hai tuyến đò.
Không có cách nào giữ lại 3 tuyến đò trở lên.
Ràng buộc:
Có 30% số test của bài có k≤10.
40% số test của bài có k≤2000.
30% số test còn lại không có giới hạn gì thêm.	
---------------------HẾT---------------------
Cán bộ coi thi không giải thích gì thêm.