Đề thi chọn học sinh giỏi THPT cấp tỉnh môn Tin học - Năm học 2020-2021 - Sở GD&ĐT Ninh Bình (Có đáp án)

SỞ GIÁO DỤC VÀ ĐÀO TẠO
TỈNH NINH BÌNH
ĐỀ THI CHÍNH THỨC
ĐỀ THI CHỌN HỌC SINH GIỎI THPT CẤP TỈNH
NĂM HỌC 2020-2021
MÔN: TIN HỌC
Ngày thi: 07/10/2020
(Thời gian 180 phút, không kể thời gian phát đề)
Đề thi gồm 04 câu, trong 04 trang
Họ và tên thí sinh :........................................................Số báo danh:................................
Họ và tên, chữ ký:	Giám thị số 1:...................................................................................
	Giám thị số 2:.......................................................................................
Tổng quan đề thi
Bài
Tên bài
File
chương trình
File
dữ liệu vào
File kết quả
Thời gian/ Bộ nhớ
1
Số dư
DARR.*
DARR.INP
DARR.OUT
1 giây/ test, 1024Mb
2
Dãy số
DELARR.*
DELARR.INP
DELARR.OUT
1 giây/ test, 1024Mb
3
Sơ tán
EVA.*
EVA.INP
EVA.OUT
1 giây/ test, 1024Mb
4
Vùng đất
LAND.*
LAND.INP
LAND.OUT
1 giây/ test, 1024Mb
Dấu * được thay bởi PAS hoặc CPP của ngôn ngữ lập trình tương ứng là Pascal hoặc C++
Hãy lập trình giải các bài toán sau:
Bài 1 (5,0 điểm): Số dư
Bạn được cho một dãy số nguyên dương A=(a1,a2,,an). 
Yêu cầu: Hãy tìm giá trị lớn nhất của phần dư trong phép chia số nguyên ai cho aj. Với 1≤i,j≤n và ai≥aj.
Dữ liệu vào: Cho file văn bản DARR.INP
Dòng đầu tiên chứa số nguyên dương n - độ dài của dãy (1≤n≤200000).
Dòng thứ hai chứa n số nguyên lần lượt là a1,a2,,an (1≤ai≤106).
(Mỗi số trên một dòng cách nhau bởi một dấu cách)
Dữ liệu ra: Ghi ra file văn bản DARR.OUT một số nguyên là kết quả của bài toán.
Ví dụ:
DARR.INP
DARR.OUT
Giải thích
3
2 4 5
1
4 chia 2 dư 0;
5 chia 2 dư 1;
5 chia 4 dư 1;
Kết quả số dư lớn nhất là 1
Ràng buộc: 70% số test có n≤5000.
Bài 2 (5,0 điểm): Dãy số
	Cho một dãy n số nguyên có giá trị lần lượt từ 1 đến n. Bạn được thực hiện m thao tác, mỗi thao tác sẽ xóa một số khỏi dãy tại một vị trí bất kỳ. Sau mỗi thao tác xóa thì tất cả các số đằng sau chưa bị xóa sẽ được dồn về phía trước.
Yêu cầu: Cho biết vị trí cần xóa của m thao tác, viết chương trình xác định số bị xóa trong mỗi thao tác. Nếu trong một thao tác không có số nào bị xóa thì ghi ra số 0.
Dữ liệu vào: Cho file DELARR.INP
Dòng đầu tiên ghi hai số nguyên lần lượt là n, m (1≤ n, m ≤ 300000).
Dòng thứ 2 ghi m số nguyên lần lượt là các vị trí cần xóa.
(Mỗi số trên một dòng cách nhau bởi một dấu cách)
Dữ liệu ra: Ghi vào file văn bản DELARR.OUT gồm m dòng, dòng thứ i là số bị xóa ở lượt thứ i. (1≤ i ≤ n)
Ví dụ:
DELARR.INP
DELARR.OUT
6 3
2 4 6
2
5
0
Ràng buộc: 	30% số test có n≤100.
	30% số test có 101≤n≤10000.
	40% số test có 10001≤n≤300000.
Bài 3 (5,0 điểm): Sơ tán
Một Trung tâm nghiên có n phòng thí nghiệm đặt ngầm trong lòng đất. Các phòng thí nghiệm được đánh số từ 1 đến n (1 ≤ n ≤ 105). Trung tâm có tất cả m đoạn đường hầm hai chiều nối trực tiếp hai phòng với nhau (1 ≤ m ≤ 105), sao cho từ một phòng bất kỳ có thể đi đến n-1 phòng còn lại (có thể phải đi qua một số phòng trung gian). Không có đoạn đường hầm nào nối một phòng với chính nó, nhưng có thể có nhiều đoạn đường hầm cùng nối 2 phòng với nhau. Có k phòng có lối thoát hiểm lên trên mặt đất (1 ≤ k ≤ n). Trong trường hợp phải sơ tán khẩn cấp, tất cả các nhân viên phải tập trung ở những phòng có lối thoát hiểm lên trên mặt đất. 
Yêu cầu: Hãy xác định quãng đường ngắn nhất để nhân viên mỗi phòng tập trung về phòng có lối thoát hiểm lên trên mặt đất trong trường hợp phải sơ tán khẩn cấp.
Dữ liệu vào: Cho file văn bản EVA.INP.
Dòng đầu tiên chứa 2 số nguyên n và k.
Dòng thứ 2 chứa k số nguyên khác nhau cho biết các phòng có cửa thoát hiểm.
Dòng thứ 3 chứa số nguyên m.
Mỗi dòng trong m dòng tiếp theo chứa 3 số nguyên xác định cặp phòng có đoạn đường hầm nối trực tiếp và độ dài của đoạn đường hầm đó.
(Mỗi số trên một dòng cách nhau bởi một dấu cách)
Dữ liệu ra: Ghi ra file văn bản EVA.OUT một dòng chứa n số nguyên, số thứ i xác định quãng đường ngắn nhất để nhân viên phòng i đi được tới phòng có lối thoát hiểm lên trên mặt đất. (1 ≤ i ≤ n).
(Mỗi số trên một dòng cách nhau bởi một dấu cách)
Ví dụ:
EVA.INP
EVA.OUT
10 2
10 8 
10
6 7 1
7 5 1
5 8 1
8 1 1
1 10 1
10 3 1
3 4 1
4 9 1
9 2 1
3 9 1
1 3 1 2 1 3 2 0 2 0
Ràng buộc: 	30% số test có n≤10.000 và k =1.
	30% số test có 101≤n≤5000.
	40% số test có 5000<n≤100000 và k < 10.
Bài 4 (5,0 điểm): Vùng đất
	Do hiện tượng khí hậu ấm lên trên toàn cầu, mực nước biển dâng theo từng năm. Các nhà khoa học đã mô hình hóa quá trình ngập nước của một vùng đất. Giả sử vùng đất đã mô hình hóa quá trình ngập nước được chia thành m x n ô vuông nhỏ. Do có nhiều mạch ngầm thông với biển nên khi nước biển dâng bằng độ cao của một ô vuông thì coi như toàn bộ ô vuông đất bị ngập. Các nhà khoa học đã tính được độ cao của toàn bộ vùng đất và dự đoán được mức nước biển dâng sau từng năm, từ đó dự báo được năm (thời điểm) mà ô đất sẽ bị ngập. 
Yêu cầu: Cho bảng số liệu dự báo thời gian ngập nước của các ô đất. Hãy cho biết có bao nhiêu mảnh đất không bị ngập nước trong các năm cần báo cáo. Một mảnh đất không bị ngập nước là tập hợp các ô vuông không bị ngập nước liên thông cạnh với nhau.
Ví dụ xét một vùng đất có kích thước 4 x 5 ô, giá trị trong mỗi ô là năm mà nước sẽ ngập ô đó. Các ô màu trắng chỉ nước ngập và các ô màu đen chỉ nước không ngập. Vào năm thứ nhất có 2 mảnh đất không bị ngập nước và vào năm thứ hai có 3 mảnh đất không ngập nước:
1
2
3
3
1
1
3
2
2
1
2
1
3
4
3
1
2
2
2
2
Năm 1
1
2
3
3
1
1
3
2
2
1
2
1
3
4
3
1
2
2
2
2
Năm 2
Dữ liệu vào: Cho file văn bản LAND.INP
Dòng đầu tiên ghi hai số nguyên dương m, n (1≤ m, n ≤ 1000).
m dòng tiếp theo mỗi dòng ghi n số nguyên, số thứ j của dòng (i+1) là một số thể hiện năm mà ô đất (i,j) bị ngập. (1≤ i ≤ m, 1≤ j ≤ n).
Dòng tiếp theo ghi một số nguyên k là số lượng năm cần báo cáo (1≤ k ≤105).
Dòng cuối ghi k số nguyên là danh sách các năm cần báo cáo số lượng mảnh đất không bị ngập nước. Các năm được sắp xếp theo thứ tự tăng dần.
(Mỗi số trên một dòng cách nhau bởi một dấu cách)
Dữ liệu ra: Ghi trong file văn bản LAND.OUT gồm k số trên một dòng lần lượt là số lượng mảnh đất không bị ngập nước của các năm trong danh sách.
(Mỗi số trên một dòng cách nhau bởi một dấu cách)
Ví dụ:
LAND.INP
LAND.OUT
4 5
1 2 3 3 1 
1 3 2 2 1 
2 1 3 4 3 
1 2 2 2 2 
5 
1 2 3 4 5
2 3 1 0 0
Ràng buộc: 	30% số test có k=1.
	30% số test có k≤10.
	40% số test có 10<k ≤105.
-----Hết-----