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

ĐỀ THI CHÍNH THỨC
SỞ GD&ĐT NINH BÌNH
ĐỀ THI CHỌN HỌC SINH GIỎI, HỌC VIÊN GIỎI LỚP 12 CẤP TỈNH NĂM HỌC 2018-2019
MÔN: TIN HỌC
Ngày thi: 15/12/2018
(Thời gian 180 phút, không kể thời gian giao đề)
Đề thi gồm 04 câu trong 03 trang
TỔNG QUAN ĐỀ THI
Câu
Chương trình
Dữ liệu vào
Dữ liệu ra
Thời gian / bộ nhớ
Câu 1
ROBOT.*
ROBOT.INP
ROBOT.OUT
1 giây/test/1024 MB
Câu 2
MAXROAD.*
MAXROAD.INP
MAXROAD.OUT
1 giây/test/1024 MB
Câu 3
SUB.*
SUB.INP
SUB.OUT
1 giây/test/1024 MB
Câu 4
CITY.*
CITY.INP
CITY.OUT
1 giây/test/1024 MB
Lưu ý: - Phần mở rộng của chương trình (.*) có thể là (.PAS) hoặc (.CPP) phụ thuộc vào ngôn ngữ lập trình là Pascal hoặc C++.
	 - Hai số liên tiếp trên cùng một hàng cách nhau ít nhất một khoảng trắng.
ĐỀ BÀI
Bài 1 (7 điểm): Robot thông minh. 
Steve có một con robot rất thông minh. Steve lập trình cho con robot của mình di chuyển trên một mặt phẳng tọa độ. Ban đầu con robot đứng ở tọa độ (0; 0) và di chuyển theo một lộ trình xác định trong một dãy chỉ chứa bốn loại kí tự U, D, L, R. Mỗi kí tự trong dãy tương ứng với bước di chuyển tiếp theo của robot như sau:
‘U’: (x; y) → (x; y + 1)
‘D’: (x; y) → (x; y - 1)
‘L’: (x; y) → (x – 1; y)
‘R’: (x; y) → (x + 1; y)
Yêu cầu: Cho tọa độ Steve đang đứng và xâu S, xác định xem liệu con robot có gặp được Steve không.
Dữ liệu vào: Từ file ROBOT.INP gồm: 
- Dòng đầu chứa 2 số nguyên x, y là tọa độ của Steve đang đứng (x, y ≠ 0).
- Dòng tiếp theo chứa xâu S.
Dữ liệu ra: Ghi ra file ROBOT.OUT là YES hoặc NO tương ướng với việc robot có đến được vị trí của Steve đang đứng hay không.
Ví dụ:
ROBOT.INP
ROBOT.OUT
1 1
RU
YES
1 2
RU
NO
Giới hạn: 80% test có giá trị |x|, |y| ≤ 100 và độ dài của dãy kí tự không quá 100. 
	 20% test có giá trị |x|, |y| ≤ 105 và độ dài của dạy kí tự không quá 105.
Bài 2 (7 điểm): Con đường của Max.
Max là cậu bé thông minh, cậu rất thích học toán. Một hôm cậu được học khái niệm số nguyên tố, cậu rất thích thú. Max đã quyết định tìm ra tất cả các số nguyên tố trong một dãy số nguyên dương bất kỳ và sắp xếp lại những số nguyên tố này theo chiều tăng dần để tạo thành một con đường đi của riêng mình gọi là “Con đường của Max”. Bạn hãy giúp Max chỉ ra con đường đó.
Dữ liệu vào: Từ file MAXROAD.INP gồm:
- Dòng đầu chứa số tự nhiên N là số phần tử của dãy.
- Dòng tiếp theo chứa N phần tử của dãy A1, A2,, An (có ít nhất 1 số nguyên tố).
Dữ liệu ra: Ghi ra file MAXROAD.OUT là con đường của Max gồm các số nguyên tố trong dãy được sắp xếp theo chiều tăng dần.
Ví dụ: 
MAXROAD.INP
MAXROAD.OUT
10
2 4 8 3 10 5 2 9 15 4
2 2 3 5
Giới hạn: 80% test có giá trị 1 ≤ N, Ai ≤ 100.
 20% test có giá trị 1 ≤ N≤ 109 và 1 ≤ Ai ≤ 105.
Bài 3 (4 điểm): Dãy con. 
	Cho một dãy số nguyên dương gồm N phần tử A1, A2, ..., An và một số nguyên dương K.
	Yêu cầu: Tìm độ dài nhỏ nhất của dãy con chứa các phần tử liên tiếp của dãy đã cho mà có tổng các phần tử lớn hơn hoặc bằng K.
	Dữ liệu vào: Từ file SUB.INP gồm:
- Dòng đầu chứa hai số nguyên dương N và K. 
- Dòng tiếp theo chứa N phần tử của dạy A1, A2,, An.
	Dữ liệu ra: Ghi ra file SUB.OUT một số nguyên là độ dài của dãy con tìm được.
	Ví dụ:
SUB.INP
SUB.OUT
10 15
5 1 3 5 10 7 4 9 2 8
2
Giới hạn: 80% test có giá trị 1 ≤ N, Ai ≤ 100 và 1 ≤ K ≤ 105.
 20% test có giá trị 1 ≤ N, Ai ≤ 106 và 1 ≤ K ≤ 109.
Bài 4 (2 điểm): Đi thăm thành phố.
Baoma là tổng thống của đất nước mà Ben đang sinh sống. Một ngày nọ, Baoma đi thăm thành phố mà Ben làm việc. Để đảm bảo an ninh nên một số tuyến đường giao thông bị cấm tạm thời, do đó công việc chở hàng của Ben cũng gặp chút vấn đề.
Khi Baoma di chuyển trên một con đường nào đó, cảnh sát sẽ chặn 2 đầu đường và không cho phép bất cứ ai đi vào con đường trước khi Baoma đi ra khỏi con đường đó. Tuy nhiên những ai đã đi vào con đường đó trước khi Baoma đi vào vẫn có thể tiếp tục di chuyển và rời khỏi con đường này. 
Ben vẫn cố gắng làm tốt công việc chở hàng của mình. Anh biết trước lịch trình của Baoma và tính toán kĩ kế hoạch cho mình. Thành phố được mô phỏng bằng các nút giao thông và các con đường 2 chiều.
Yêu cầu: Hãy viết chương trình tính toán thời gian tối thiểu để Ben hoàn thành công việc của mình. Biết rằng Baoma xuất phát trước Ben K phút.
Dữ liệu vào: Từ file CITY.INP gồm:
- Dòng đầu tiên chứa 2 số nguyên N và M (1 ≤ N ≤ 105, 1 ≤ M ≤ 2.105), trong đó N là số nút giao thông của thành phố, M là số con đường.
- Dòng thứ hai chứa 4 số nguyên A, B, K và G (1 ≤ A, B, G ≤ N, 1 ≤ K ≤ 103), với A và B là nút giao thông mà Ben xuất phát và nút giao thông mà Ben đến, K là khoảng thời gian chênh lệch khi xuất phát của Baoma và Ben, G là số nút giao thông trên đường đi của Baoma.
- Dòng thứ ba chứa G số nguyên là các nút giao thông mà Baoma sẽ lần lượt đi qua. Nó đảm bảo luôn tồn tại và Baoma đi qua mỗi đường phố nhiều nhất 1 lần.
- M dòng tiếp theo mỗi dòng chứa 3 số U, V, W biểu diễn đường đi từ nút U đến V mất W phút.
Dữ liệu ra: Ghi ra file CITY.OUT một số duy nhất là thời gian tối thiểu để Ben hoàn thành công việc của mình.
Ví dụ:
CITY.INP
CITY.OUT
6 6
1 6 20 4
5 3 2 4
1 2 2
2 3 8
2 4 3
3 6 10
3 5 15
2 6 20
21
------------- Hết -------------
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: