Đề 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 (Đề 1) (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: 11/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Ứ NHẤT 
Tên bài
File chương trình
File dữ liệu vào
File kết quả
Bài 1
Số sinh đôi
TWINS.*
TWINS.INP
TWINS.OUT
Bài 2
Dãy con
SUBSEQ.*
SUBSEQ.INP
SUBSEQ.OUT
Bài 3
Trạm bơm xăng
PETROL.*
PETROL.INP
PETROL.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. Số sinh đôi (6 điểm)
Trong lý thuyết số, hai số nguyên tố p và q được gọi là cặp số nguyên tố sinh đôi nếu q – p = 2. Ví dụ: các cặp số (3, 5), (5, 7), (11, 13), (17, 19) là các cặp sinh đôi. Trong trường hợp tổng quát, với số nguyên dương k cho trước, cặp số nguyên tố p và q được gọi là sinh đôi nếu q – p = k. Ví dụ: với k = 4 cặp số nguyên tố (3, 7) được gọi là sinh đôi.
Yêu cầu: Cho n và k (1 ≤ k ≤ n ≤ 106). Hãy xác định số cặp sinh đôi trong phạm vi từ 1 đến n (thỏa mãn q – p = k).
Dữ liệu: Vào từ file văn bản TWINS.INP gồm một dòng chứa 2 số nguyên n và k.
Kết quả: Ghi ra file văn bản TWINS.OUT một số nguyên là số lượng cặp sinh đôi tìm được.
Ví dụ:
TWINS.INP
TWINS.OUT
17 2
3
Ràng buộc:
Có 70% số test ứng với 70% số điểm của bài có n ≤ 102;
Có 30% số test ứng với 30% số điểm của bài có n ≤ 106.
Câu 2: Dãy con (7 điểm)
Một dãy N các số nguyên dương (ai ≤ 109) được gọi là dãy chia hết hoàn toàn nếu chia hết cho với mọi j > i. Ví dụ: Dãy 3, 15, 60, 720 là một dãy chia hết hoàn toàn.
Một dãy con của một dãy cho trước được thiết lập bằng cách xóa đi một số phần tử nào đó của dãy (giữ nguyên thứ tự). Ví dụ: với dãy gồm 9 phần tử: 2, 3, 7, 8, 14, 39, 145, 76, 320 thì 3, 7, 14, 76 là một dãy con nhưng 3, 14, 7 không là dãy con.
Yêu cầu: Tìm dãy con chia hết hoàn toàn có độ dài lớn nhất.
Dữ liệu vào: Cho trong file văn bản SUBSEQ.INP có cấu trúc:
* Dòng đầu tiên ghi số nguyên dương N;
* Dòng tiếp theo ghi N số nguyên các số cách nhau ít nhất một dấu cách.
Dữ liệu ra: Ghi ra file văn bản SUBSEQ.OUT số nguyên M là độ dài dãy con chia hết hoàn toàn có độ dài lớn nhất.
Ví dụ 1:
SUBSEQ.INP
SUBSEQ.OUT
9
2 3 7 8 14 39 145 76 320
3
Giải thích: Dãy con chia hết hoàn toàn dài nhất là dãy: 2 8 320 (có độ dài bằng 3).
Ví dụ 2:
SUBSEQ.INP
SUBSEQ.OUT
10
2 3 4 8 9 27 145 81 320 5
4
Giải thích: Dãy con chia hết hoàn toàn dài nhất có độ dài là 4; có thể là dãy: 2 4 8 320 hoặc 3 9 27 81.
Ràng buộc:
Có 70% số test ứng với 70% số điểm của bài có N ≤ 20;
Có 30% số test ứng với 30% số điểm của bài có N ≤ 103.
Bài 3. Trạm bơm xăng (7 điểm)
Dọc đường quốc lộ 1A có N trạm bơm xăng. Để đơn giản ta có thể coi con đường như là trục tọa độ một chiều. Một đơn vị tọa độ tương ứng với 1 km. Trạm xăng thứ i có tọa độ xi và có dung tích bể chứa là hi.
Sau một thời gian hoạt động, người ta cần phải giảm số lượng các trạm xăng không hiệu quả. Một trạm i được coi là không hiệu quả nếu như tồn tại một trạm j trong khoảng cách D km về bên trái hoặc bên phải nó có dung tích bể chứa hj thỏa mãn hj ≥ 2*hi.
Viết chương trình xác định có bao nhiêu trạm bơm xăng không hiệu quả.
Dữ liệu: Vào từ file văn bản PETROL.INP
Dòng đầu tiên ghi hai số nguyên dương N, D (1 ≤ N ≤ 5*104, 1 ≤ D ≤ 109);
N dòng tiếp theo, dòng thứ i ghi hai số nguyên xi, hi (1 ≤ xi, hi ≤ 109);
Dữ liệu đảm bảo rằng vị trí của các trạm xăng là khác nhau. Hai số liên tiếp trên cùng một dòng cách nhau bằng khoảng trống.
Kết quả: Ghi ra file văn bản PETROL.OUT một số nguyên duy nhất là số lượng trạm bơm xăng không hiệu quả.
Ví dụ:
PETROL.INP
PETROL.OUT
6 4
10 3
6 2
5 3
9 7
3 6
11 2
2
Giải thích: Trong ví dụ trên các trạm đặt ở vị trí x=5 và x=6 là các trạm không hiệu quả.
PETROL.INP
PETROL.OUT
4 2
1 4
2 1
3 2
5 4
2
Giải thích: Trong ví dụ trên các trạm đặt ở vị trí x=2 và x=3 là trạm không hiệu quả.
Ràng buộc:
Có 50% số test ứng với 50% số điểm của bài có N ≤ 5*103;
Có 50% số test ứng với 50% số điểm của bài có N ≤ 5*104.
-----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:.....................................................................................