HSG lớp 9 Đồng Tháp 2017-2018

SỞ GIÁO DỤC VÀ ĐÀO TẠO TỈNH ĐỒNG THÁP ĐỀ CHÍNH THỨC
(Đề gồm có 02 trang)

KỲ THI CHỌN HỌC SINH GIỎI LỚP 9 CẤP TỈNH Năm học 2017 - 2018
Môn: Tin học - Ngày thi: 25/3/2018
Thời gian làm bài: 150 phút, không kể thời gian phát đề

---

Tổng quan đề thi

Tên bài	Tên tệp chương trình	Tên tệp dữ liệu vào	Tên tệp dữ liệu ra
Bài 1. Số T-Prime	BL1.*	TPRIME.INP	TPRIME.OUT
Bài 2. Marathon	BL2.*	MARATHON.INP	MARATHON.OUT
Bài 3. Phố đi bộ	BL3.*	PHODIBO.INP	PHODIBO.OUT

Ghi chú: dấu * đại diện cho phần mở rộng, tuỳ theo ngôn ngữ lập trình có thể là PAS hoặc CPP. Thời gian thực hiện chương trình không quá 1 giây.

Bài 1. Số T-Prime (6,0 điểm)

Bạn Nam rất yêu thích toán học, đặc biệt là thích tìm hiểu về số học. Một ngày nọ, trong lúc giải một bài toán số học, bạn Nam phát hiện ra trong các số mà mình tìm được có rất nhiều số có đặc điểm là chúng có đúng ba ước số nguyên dương khác nhau, và bạn Nam gọi những số này là số T-Prime.

Yêu cầu: Hãy lập trình giúp bạn Nam đếm xem có bao nhiêu số T-Prime (tức là số có đúng ba ước số nguyên dương khác nhau) có giá trị không vượt quá số nguyên n cho trước.

Dữ liệu vào: Cho từ tệp văn bản TPRIME.INP gồm một dòng ghi số nguyên dương n.

Kết quả: Ghi ra tệp văn bản TPRIME.OUT gồm một dòng ghi một số nguyên là số lượng số T-Prime đếm được.

Ví dụ:

TPRIME.INP	TPRIME.OUT
6	1

Giải thích: Có một số T-Prime nhỏ hơn hoặc bằng 6 là số 4 (có đúng 3 ước số: 1, 2, 4).

Ràng buộc:

• Có 70% số test ứng với 70% số điểm có giá trị n ≤ 10³.
• Có 20% số test ứng với 20% số điểm có giá trị n ≤ 10⁵.
• Có 10% số test ứng với 10% số điểm có giá trị n ≤ 10⁹.

Bài 2. Marathon (7,0 điểm)

Trong cuộc chạy bộ dã ngoại chào mừng ngày thành lập Đoàn 26/3 có n đoàn viên tham gia được đánh số báo danh từ 1 đến n, đoàn viên thứ i có thời gian chạy là aᵢ (i = 1..n). Ban tổ chức quy định về cách thức chọn các đoàn viên để trao giải thưởng như sau:

• Phải có ít nhất một đoàn viên được chọn để trao thưởng.
• Nếu một đoàn viên nào đó được chọn để trao thưởng thì tất cả các đoàn viên có thời gian chạy bằng hoặc thấp hơn thời gian chạy của đoàn viên được chọn cũng phải được trao thưởng.

Yêu cầu: Hãy viết chương trình đếm xem có bao nhiêu cách chọn các đoàn viên để trao thưởng.

Dữ liệu vào: Cho từ tệp văn bản MARATHON.INP gồm hai dòng:

• Dòng thứ nhất ghi số nguyên dương n.
• Dòng thứ hai ghi n số nguyên a₁, a₂, …, aₙ (1 ≤ aᵢ ≤ 10⁶). Giữa các số cách nhau một khoảng cách.

Kết quả: Ghi ra tệp văn bản MARATHON.OUT gồm một dòng ghi một số nguyên là số cách chọn các đoàn viên để trao thưởng.

Ví dụ:

MARATHON.INP	MARATHON.OUT
4 2 3 3 1	3

Giải thích: Trong ví dụ, có ba cách chọn như sau:

• Cách 1: Chọn đoàn viên thứ 4.
• Cách 2: Chọn đoàn viên thứ 1 và thứ 4.
• Cách 3: Chọn tất cả đoàn viên.

Ràng buộc:

• Có 70% số test ứng với 70% số điểm có giá trị n ≤ 10³.
• Có 20% số test ứng với 20% số điểm có giá trị n ≤ 10⁶.
• Có 10% số test ứng với 10% số điểm có giá trị n ≤ 10⁷.

Bài 3. Phố đi bộ (7,0 điểm)

Tết năm nay, thủ phủ đất Sen hồng có phố đi bộ, dọc theo tuyến phố có n địa điểm vui chơi, các địa điểm được đánh số lần lượt từ 1 tới n tính từ đầu phố. Sắp tới trên tuyến phố được trang bị thêm xe điện để đưa đón du khách. Ban đầu, ban quản lí dự kiến bố trí hai trạm dừng tại hai trong số n địa điểm vui chơi, đồng thời để hai trạm dừng này không được quá gần nhau, khoảng cách giữa hai trạm phải lớn hơn r.

Yêu cầu: Đếm số cặp điểm vui chơi trên tuyến phố mà ban quản lí có thể chọn để đặt hai trạm dừng chân sao cho khoảng cách giữa hai trạm lớn hơn r.

Dữ liệu vào: Cho từ tệp văn bản PHODIBO.INP gồm hai dòng:

• Dòng thứ nhất chứa hai số nguyên n và r (2 ≤ n ≤ 3×10⁵; 1 ≤ r ≤ 10⁹).
• Dòng thứ hai chứa n số nguyên d₁, d₂, …, dₙ (1 ≤ d₁ < d₂ < … < dₙ ≤ 10⁹); với dᵢ là khoảng cách từ điểm vui chơi thứ i tới đầu con phố.

Các số ghi trên một dòng cách nhau một khoảng cách.

Kết quả: Ghi ra tệp văn bản PHODIBO.OUT gồm một dòng ghi một số nguyên là số cặp điểm mà ban quản lí có thể chọn để đặt hai trạm dừng chân.

Ví dụ:

PHODIBO.INP	PHODIBO.OUT	Giải thích
4 4 1 3 5 8	2	Có 2 phương án chọn đó là các cặp (1, 4) và (2, 4)

Ràng buộc:

• Có 60% số test ứng với 60% số điểm có giá trị 2 ≤ n ≤ 5000.
• Có 40% số test ứng với 40% số điểm có giá trị 5000 < n ≤ 3×10⁵.