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

SỞ GD&ĐT 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 2019 - 2020
MÔN: TIN HỌC
Ngày thi: 12/9/2019
(Thời gian 180 phút, không kể thời gian phát đề)
Đề thi gồm 03 câu, trong 03 trang
TỔNG QUAN BÀI THI NGÀY THỨ HAI 
Tên bài
File chương trình
File dữ liệu vào
File kết quả
Câu 1
Cây keo
TREE.*
TREE.INP
TREE.OUT
Câu 2
Nhảy vòng
JUMP.*
JUMP.INP
JUMP.OUT
Câu 3
Trải nghiệm
TIME.*
TIME.INP
TIME.OUT
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 1. Cây keo (6,0 điểm) 
Trong một trang trại chăn nuôi người ta trồng kèm N cây keo lai (cây keo lai là nguyên liệu làm giấy) theo hình tròn bao quanh khu vực chăn nuôi, các cây keo lai được đánh số từ 1 đến N theo chiều kim đồng hồ. Cây ở vị trí i có giá trị là ai (i=1,2,,N), giá trị có thể là số âm nếu giá bán của cây bé hơn chi phí cắt, dọn cây. Đến mùa thu hoạch, để tiện cho máy móc hoạt động người ta cần tìm cách chọn một dãy liên tiếp một số cây keo lai (theo chiều kim đồng hồ) để cắt.
Yêu cầu: Tìm một dãy liên tiếp các cây keo lai sao cho tổng giá trị của các cây này là lớn nhất.
Dữ liệu: Vào từ file văn bản TREE.INP:
Dòng đầu tiên ghi số nguyên dương N (N£106);
Dòng thứ i trong số N dòng tiếp theo ghi số ai (
Kết quả: Ghi ra file văn bản TREE.OUT:
Dòng đầu tiên ghi tổng giá trị các cây keo tìm được.
Dòng thứ hai ghi hai số nguyên d và c cách nhau ít nhất một khoảng trắng trong đó d là chỉ số của cây keo đầu tiên của dãy còn c là số lượng các cây keo tìm được. (Nếu có nhiều dãy thỏa mãn thì d và c là kết quả của dãy đầu tiên tìm thấy)
Ví dụ:
TREE.INP
TREE.OUT
7
2
-4
1
-7
4
6
-1
11
5 4
Ràng buộc:
Có 70% số test ứng với 70% số điểm của bài có 
Có 30% số test ứng với 30% số điểm của bài có 
Câu 2. Nhảy vòng (7,0 điểm)
	Trên mặt phẳng vẽ N vòng tròn được đánh số thứ tự từ 1 đến N. Tại vòng tròn i người ta điền số nguyên dương ai. Hai số trên hai vòng tròn tùy ý không nhất thiết phải khác nhau. Tiếp đến người ta vẽ các mũi tên, mỗi mũi tên hướng từ một vòng tròn đến một vòng tròn khác. Quy tắc vẽ mũi tên là: Nếu có ba số ai, aj, ak thỏa mãn ak = ai + aj thì vẽ mũi tên hướng từ vòng tròn i đến vòng tròn k và mũi tên hướng từ vòng tròn j đến vòng tròn k. Người chơi chỉ được di chuyển từ một vòng tròn đến một vòng tròn khác nếu có mũi tên xuất phát từ một trong số các vòng tròn, di chyển theo cách mũi tên đã vẽ để đi đến các vòng tròn khác. Người thắng cuộc sẽ là người tìm được cách di chuyển qua nhiều vòng tròn nhất.
Ví dụ: Với 5 vòng tròn và các số trong vòng tròn là 1, 2, 8, 3, 5, trò chơi được trình bày trong hình dưới đây:
	Khi đó có thể di chuyển được nhiều nhất qua 4 vòng tròn - tính cả vòng tròn đầu (tương ứng với đường di chuyển được tô đậm trên hình vẽ).
Yêu cầu: Hãy xác định xem trong trò chơi mô tả ở trên, nhiều nhất có thể di chuyển được qua bao nhiêu vòng tròn.
Dữ liệu: vào từ file JUMP.INP gồm
Dòng đầu chứa số nguyên n (3 ≤ n ≤ 1000);
Dòng thứ hai chứa dãy số nguyên dương a1, a2, ..., an (ai ≤ 109, i=1, 2,..., n).
Hai số liên tiếp trên một dòng được ghi cách nhau bởi một khoảng trắng.
Kết quả: Ghi ra file JUMP.OUT một số duy nhất là số lượng vòng tròn trên đường di chuyển tìm được.
Ví dụ:
JUMP.INP
JUMP.OUT
5
1 2 8 3 5
4
Ràng buộc:
Có 30% số test ứng với 30% số điểm của bài có 
Có 30% số test ứng với 30% số điểm của bài có 
Có 40% số test ứng với 40% số điểm của bài có 
Câu 3. Trải nghiệm (7.0 điểm)
Trong một cuộc đi trải nghiệm tại Hà Nội các bạn trong lớp của Quang rất hào hứng, chuẩn bị mọi điều kiện để chuyến đi diễn ra thật vui vẻ, chuyến xe du lịch được xuất phát tại trường và xe đi qua các thành phố như Ninh Bình, Hà Nam một cách rất nhanh chóng. Nhưng khi xe du lịch đi vào Thành phố Hà Nội thì trời mưa to, một số tuyến phố bị ngập sâu. 
Thành phố Hà Nội có hệ thống giao thông gồm n nút giao thông và m đường nối hai chiều. Mỗi tuyến đường có mi nối 2 nút giao thông u, v có độ ngập sâu hi và thời gian đi ti, tất nhiên nếu tuyến đường ngập quá sâu thì xe đi qua có thể bị chết máy hoặc hỏng hóc.
Yêu cầu: Bạn hãy tìm hành trình để xe di chuyển từ X đến Y đi qua các tuyến đường có độ ngập sâu bé nhất có thể (trên mỗi hành trình đi từ X đến Y có một giá trị D là tuyến đường ngập sâu nhất trong các tuyến đường của hành trình đó, bạn hãy tìm giá trị D bé nhất có thể). Nếu có nhiều hành trình đi từ X đến Y với giá trị D đó bạn hãy tìm hành trình có thời gian ngắn nhất (biết rằng khi chưa ngập luôn tồn tại đường đi từ X đến Y).
Dữ liệu: Vào từ file văn bản TIME.INP
- Dòng đầu tiên là n, X, Y 
- Dòng tiếp theo là số m (2 ≤ n, m ≤ 1000) 
- Trong m dòng tiếp theo, tại dòng thứ i gồm bốn số nguyên u, v, h, t (đường đi từ u đến v có độ ngập sâu h(cm) và thời gian đi qua nó là t(phút)). (1≤ u,v ≤ n, 1≤ h, t ≤ 1000)
Dữ liệu: Ghi ra file văn bản TIME.OUT 
- Gồm 2 số nguyên là giá trị ngập sâu bé nhất và thời gian ngắn nhất tương ứng – mỗi số trên một dòng.
4
3
6
1
2
5
Ví dụ:
TIME.INP
TIME.OUT
6 2 4
10
2 1 900 100
5 2 400 700
1 5 200 600
6 3 200 200
4 5 100 100
2 6 300 400
1 6 500 200
6 5 200 300
3 4 200 300
3 5 300 100
300
800
Giải thích: Với độ ngập sâu lớn nhất là 300 thì sẽ có đường đi từ 2 đến 4 và hành trình có thời gian ngắn nhất là 2 ® 6 ® 5 ® 4 với thời gian là 800. 
-----Hết----
Họ và tên thí sinh :....................................................... Số báo danh .............................
Họ và tên, chữ ký:	Giám thị 1:.....................................................................................
 	Giám thị 2:.....................................................................................