Đề thi chọn học sinh giỏi THPT cấp tỉnh năm 2017 môn Tin học - 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 2017
MÔN: TIN HỌC
Ngày thi: 25/4/2017
(Thời gian 180 phút, không kể thời gian phát đề)
Đề thi gồm 03 câu, trong 02 trang
Tổng quan bài thi
Bài
Tên bài
Tên Chương trình
Input
Output
Thời gian/Test
1
Đánh số trang
DIGITS.*
DIGITS.INP
DIGITS.OUT
1 giây
2
Xổ số
LOTT.* 
 LOTT.INP 
LOTT.OUT 
1 giây
3
Các cửa hàng
SHOPS.*
SHOPS.INP
SHOPS.OUT
1 giây
Trong đó: * là phần mở rộng PAS hoặc CPP tùy ngôn ngữ lập trình Pascal hoặc C++
Câu 1. (6.0 Điểm): Đánh số trang
Bạn An quyết định đánh số trang cho quyển sách của mình từ 1 đến N. Hãy tính số lượng chữ số 0 cần dùng, số lượng chữ số 1 cần dùng, , số lượng chữ số 9 cần dùng. 
Dữ liệu vào: Từ file văn bản DIGITS.INP gồm một dòng duy nhất chứa một số N (N ≤ 106). 
Kết quả ra: File văn bản DIGITS.OUT gồm 10 dòng, dòng thứ nhất là số 0 và số lượng chữ số 0 cần dùng, dòng thứ hai là số 1 và số lượng chữ số 1 cần dùng, , dòng thứ mười là số 9 và số lượng chữ số 9 cần dùng.
Ví dụ: 
DIGITS.INP
DIGITS.OUT
13
1
6
2
2
1
1
1
1
1
1
Câu 2 (7.0 Điểm): Xổ số 
Nhân dịp học sinh của các trường THPT về dự hội thi học sinh giỏi các tỉnh Duyên hải - Bắc Bộ lần thứ X tại Ninh Bình, Ban tổ chức hội thi quyết định mở một đợt xổ số vui chơi có thưởng. Mỗi một thí sinh tham dự lấy số báo danh của mình làm vé số. Các số báo danh là các số nguyên liên tục trong đoạn [a,b] (1≤a≤ b≤109, b-a≤105). 
Khác với các loại quay xổ số khác, ở đây ban tổ chức chọn ra N thầy giáo ở các trường, mỗi thầy nghĩ trong đầu một số nguyên dương mà mình ưa thích. Như vậy có N số nguyên dương p1, p2, ..., pn. Trưởng ban tổ chức cũng chọn một số nguyên dương K (0<K≤N).
Sau khi các thầy giáo và Trưởng ban tổ chức công bố N số nguyên dương và số K thì những bạn nào có số báo danh chia hết cho đúng K số nguyên dương trong danh sách sẽ là những bạn trúng thưởng.
Yêu cầu: Hãy cho biết số lượng những bạn trúng thưởng.
Dữ liệu: Vào từ file văn bản LOTT.INP
+ Dòng đầu tiên ghi hai số nguyên N và K (1≤N≤105).
+ Dòng thứ hai ghi N số nguyên dương p1, p2, ..., pn (1≤pi≤106).
+ Dòng thứ ba ghi hai số nguyên a và b.
Kết quả: File văn bản LOTT.OUT
+ Một dòng duy nhất ghi số lượng các bạn trúng thưởng.
Ví dụ:
LOTT.INP
LOTT.OUT
2 1
2 3
1 10
6
Câu 3 (7.0 Điểm): Các cửa hàng	 
	Tại một quốc gia nọ, có một đường phố chạy vòng theo hình tròn với chu vi 106 mét. Có N (1£ N £ 1000) ngôi nhà dân dọc theo đường phố. Vị trí của mỗi ngôi nhà được mô tả như một số nguyên, tính theo chiều kim đồng hồ từ vị trí chính Bắc là vị trí 0. Một công ty bán hàng muốn xây dựng K (1 ≤ K ≤ 1000) cửa hàng dọc theo đường phố để phục vụ dân cư dọc đường phố này. Ban quản lý công ty muốn biết khoảng cách ngắn nhất có thể từ một ngôi nhà bất kì đến cửa hàng nó gần nhất là bao xa (Giả sử rằng, người ta chỉ có thể đi đến các cửa hàng bằng đường phố nói trên). Gọi D là giá trị lớn nhất của các khoảng cách từ mỗi ngôi nhà đến cửa hàng gần nó nhất. Tìm D nhỏ nhất có thể. 
Yêu cầu: Đưa ra giá trị nhỏ nhất của D.
Dữ liệu:
+ Dòng đầu chứa số nguyên dương N.
+ Trong N dòng tiếp theo, dòng thứ i chứa một số nguyên là vị trí của ngôi nhà thứ i (0 £ i < 106) tính từ vị trí chính Bắc là vị trí 0. Không có hai ngôi nhà nào cùng vị trí.
+ Dòng cuối cùng chứa số nguyên K, là số cửa hàng cần xây dựng. Chú ý, vị trí cửa hàng có thể được đặt vào vị trí của một ngôi nhà nào đó.
Kết quả: In ra số nguyên duy nhất D.
Ràng buộc: Có 30% test ứng với 30% điểm của bài có giá trị N < 10.
Ví dụ:
SHOPS.INP
SHOPS.OUT
4 
0
67000
68000
77000
2
5000
-----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:.....................................................................................