Đề thi chọn học sinh giỏi THPT cấp tỉnh môn Tin học - Năm học 2018-2019 - 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 2018 - 2019
MÔN: TIN HỌC
Ngày thi: 12/09/2018
(Thời gian 180 phút, không kể thời gian phát đề)
Đề thi gồm 03 bài, 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ả
Bài 1
Số phản nguyên tố
PNT.*
PNT.INP
PNT.OUT
Bài 2
Khám phá Ninh Bình
CRUISE.*
CRUISE.INP
CRUISE.OUT
Bài 3
Mua hoa
MDAY.*
MDAY.INP
MDAY.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++
Viết chương trình giải các bài toán sau:
Bài 1 (6,0 điểm). Số phản nguyên tố
Một số n gọi là số phản nguyên tố nếu số ước số của nó là nhiều nhất trong n số tự nhiên đầu tiên. 
Yêu Cầu: Cho số K, hãy ghi ra số phản nguyên tố lớn nhất nhỏ hơn hoặc bằng K.
Dữ liệu: Vào từ file PNT.INP nội dung gồm:
Dòng đầu tiên là số M (1 ≤ M ≤ 10) là số các số cần tìm số phản nguyên tố lớn nhất của nó;
M dòng tiếp theo lần lượt là các số K1, K2, K3, ..., KM;
Kết quả: Ghi ra file PNT.OUT gồm M dòng: dòng thứ i là số phản nguyên tố lớn nhất nhỏ hơn hoặc bằng Ki.
Ví dụ:
PNT.INP
PNT.OUT
2
1000
100
840
96
Ràng buộc:
Có 70% số test ứng với 70% số điểm của bài có Ki ≤ 103;
Có 30% số test ứng với 30% số điểm của bài có Ki ≤ 2*104.
Bài 2. Khám phá Ninh Bình (7 điểm)
Ninh Bình là tỉnh có tiềm năng du lịch rất lớn, có N điểm du lịch có thể khám phá (đánh số từ 1 đến N). Tại một điểm du lịch bất kì có thể đi đến 2 địa điểm khác theo hướng trái (L) hoặc hướng phải (R). Tour du lịch cho khách luôn xuất phát từ điểm 1, đi theo M chỉ dẫn chỉ gồm các ký tự 'L' (bên trái) và 'R' (bên phải). Một khách du lịch muốn đi khám phá K lần theo lộ trình trên.
Viết chương trình chỉ ra điểm dừng cuối cùng của vị khách.
Dữ liệu: Vào từ file văn bản CRUISE.INP
Dòng đầu tiên ghi ba số nguyên dương N, M và K (N ≤ 103, M ≤ 5*102, K ≤ 109)
N dòng tiếp theo, mỗi dòng ghi hai số nguyên là số hiệu của điểm tiếp theo nếu xuất phát từ điểm i đi theo hướng trái hoặc hướng phải.
Dòng cuối cùng chứa M ký tự cách nhau bởi dấu trống chỉ gồm hai ký tự 'L' và 'R' là các chỉ dẫn của tour du lịch
Kết quả: Ghi ra file văn bản CRUISE.OUT một số nguyên duy nhất là số hiệu của điểm dừng cuối cùng.
Ví dụ:
CRUISE.INP
CRUISE.OUT
4 3 3
2 4
3 1
4 2
1 3
L L R
4
CRUISE.INP
CRUISE.OUT
4 3 3
2 4
3 1
4 2
1 3
L R R
2
Ràng buộc:
Có 20% số test ứng với 20% số điểm của bài có K ≤ 102.
Có 40% số test ứng với 40% số điểm của bài có K ≤ 105;
Có 40% số test ứng với 40% số điểm của bài có K ≤ 109.
Bài 3. Mua hoa (7 điểm)
Nhân dịp ngày Phụ nữ Việt Nam (20/10), trên đường đi học về Dũng muốn mua cho mẹ một bó hoa thật đẹp. Vấn đề là số tiền tiết kiệm được có hạn!
Hệ thống giao thông của thành phố có thể mô tả như là mạng lưới các tuyến xe buýt có N bến được đánh số từ 1 đến N. Chỉ có K cửa hàng bán hoa với giá khác nhau Tk. Có M tuyến xe buýt khác nhau, mỗi tuyến xe buýt sẽ giúp cho việc di chuyển giữa hai bến u và v với chi phí Duv (chi phí đi từ u đến v cũng như đi từ v đến u), giữa hai bến có không quá một tuyến xe buýt.
Yêu cầu: Hãy tính chi phí nhỏ nhất để Dũng, xuất phát từ bến A (trường học), đến bến B (nhà) và trên đường rẽ qua một trong các bến có bán hoa để mua hoa sao cho tổng chi phí mua vé xe buýt và chi phí mua hoa là nhỏ nhất.
Dữ liệu: Vào từ file văn bản MDAY.INP
* Dòng đầu tiên chứa 3 số nguyên N, M, K (2 ≤ N ≤ 5*103; 1 ≤ M ≤ 105; 1 ≤ K ≤ N);
* Dòng thứ hai chứa 2 số nguyên A và B (1 ≤ A, B ≤ N);
* Dòng thứ 3 chứa K cặp số nguyên, mỗi cặp xác định số hiệu của bến có cửa hàng hoa (nằm trong phạm vi từ 1 đến N) và giá bán một bó hoa tại cửa hàng này Tk (1 ≤ Tk ≤ 109), ở các bến khác nhau tất nhiên giá bán hoa là khác nhau;
* Mỗi dòng trong M dòng còn lại chứa 3 số nguyên u, v và Duv (1 ≤ u,v ≤ N , 1 ≤ Duv ≤ 109).
Các số liên tiếp trên cùng một dòng được ghi cách nhau bởi dấu trống.
Kết quả: Ghi ra file văn bản MDAY.OUT một số nguyên duy nhất là tổng chi phí nhỏ nhất tìm được.
Ví dụ:
MDAY.INP
MDAY.OUT
5 7 4
1 4
1 100 4 50 3 10 2 55
1 2 10
5 3 42
1 3 30
2 4 50
3 4 70
2 5 24
4 5 21
103
Giải thích: Đi theo hành trình 1 3 5 4 và mua hoa ở trạm 3.
MDAY.INP
MDAY.OUT
5 7 4
1 5
1 100 4 50 3 10 2 55
1 2 10
5 3 42
1 3 30
2 4 50
3 4 70
2 5 24
4 5 21
82
Giải thích: Đi theo hành trình 1 3 5 và mua hoa ở trạm 3.
-----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:.....................................................................................