HSG lớp 9 Bà Rịa - Vũng Tàu 2022-2023

SỞ GIÁO DỤC VÀ ĐÀO TẠO TỈNH BÀ RỊA - VŨNG TÀU ĐỀ THI CHÍNH THỨC

ĐỀ THI CHỌN HỌC SINH GIỎI CẤP TỈNH LỚP 9 Năm học 2022 - 2023
Môn: Tin học - Ngày thi: 23/03/2023
Thời gian làm bài thi: 150 phút
(Đề thi có 02 trang, 03 bài)

---

Tổng quan đề thi

Bài	Tên bài	File chương trình	File dữ liệu	File kết quả
1	Tìm ước chung lớn nhất	CDIV.*	CDIV.INP	CDIV.OUT
2	Đố vui Tin học	GIFT.*	GIFT.INP	GIFT.OUT
3	Trò chơi	GAME.*	GAME.INP	GAME.OUT

(Dấu * được thay thế bởi ngôn ngữ lập trình Pascal, C/C++ hoặc Python tương ứng)

Bài 1. Tìm ước chung lớn nhất (6 điểm)

Tên file chương trình: CDIV.*

Cho một mảng A gồm N số nguyên dương: a₁, a₂, …, a_N.

Yêu cầu: Hãy tìm hai số nguyên trong mảng A sao cho ước chung lớn nhất của 2 số đó là lớn nhất.

Dữ liệu: đọc vào từ file CDIV.INP:

• Dòng đầu tiên chứa số nguyên N (2 ≤ N ≤ 2×10⁵).
• Dòng thứ hai chứa N số nguyên aᵢ, mỗi số cách nhau một ký tự trắng (1 ≤ aᵢ ≤ 10⁶).

Kết quả: ghi ra file CDIV.OUT một số nguyên duy nhất là ước chung lớn nhất tìm được.

Ví dụ:

CDIV.INP	CDIV.OUT
6 12 5 6 4 7 10	6

Bài 2. Đố vui tin học (6 điểm)

Tên file chương trình: GIFT.*

Để tổng kết phát thưởng cho cuộc thi Đố vui tin học, Ban tổ chức có N phần quà được đánh thứ tự từ 1 tới N, phần quà thứ i có giá trị là aᵢ. Ban tổ chức yêu cầu học sinh chọn các phần quà theo quy tắc sau:

• Phần quà chọn sau phải có số thứ tự lớn hơn phần quà chọn trước đó.
• Phần quà chọn sau phải có giá trị lớn hơn phần quà chọn trước đó ít nhất K giá trị.

Yêu cầu: Hãy giúp các bạn học sinh lựa chọn theo quy tắc ban tổ chức đặt ra sao cho số lượng phần quà được chọn là nhiều nhất.

Dữ liệu: đọc vào từ file GIFT.INP:

• Dòng đầu chứa 2 số nguyên dương N và K cách nhau một ký tự trắng (N ≤ 10⁴, K ≤ 10³).
• N dòng tiếp theo, dòng thứ i chứa số nguyên dương aᵢ (aᵢ ≤ 10⁶) là giá trị của phần quà thứ i.

Kết quả: ghi ra file GIFT.OUT gồm một dòng duy nhất chứa số lượng phần quà nhiều nhất thỏa mãn yêu cầu.

Ví dụ:

GIFT.INP	GIFT.OUT
5 2 4 5 6 4 8	3

Ghi chú

Bản đánh máy trong tài liệu “50 đề thi HSG THCS” ghi K ≤ 10⁵; bản chụp đề gốc ghi K ≤ 10³ (theo đề gốc ở trên).

Bài 3. Trò chơi (8 điểm)

Tên file chương trình: GAME.*

Nhân kỷ niệm ngày thành lập Đoàn, cô Tổng phụ trách tổ chức 1 trò chơi có thưởng cho các bạn lớp 9 như sau: Có N ô vuông được vẽ thẳng hàng trên sân trường, các ô vuông được đánh số từ 1, 2, …, N. Mỗi ô vuông i (1 ≤ i ≤ N) có giá trị năng lượng là hᵢ. Một bạn học sinh đang ở ô vuông thứ i, bạn ấy có thể nhảy tới ô vuông tiếp theo các cách:

• Nếu bạn ở ô vuông thứ i thì bạn có thể nhảy đến ô vuông thứ tự i + 1, i + 2, …, i + k.
• Chi phí năng lượng của bạn tiêu hao cho 1 lần nhảy là |hⱼ − hᵢ| với hⱼ là ô vuông đích mà bạn nhảy tới.

Bạn học sinh nào di chuyển từ ô số 1 đến ô số N với chi phí năng lượng thấp nhất sẽ được cô thưởng 1 phần quà.

Yêu cầu: Hãy tìm chi phí thấp nhất để giúp các bạn học sinh nhảy từ ô vuông số 1 đến ô vuông thứ N.

Dữ liệu: đọc vào từ file GAME.INP gồm:

• Dòng đầu ghi 2 số N và K cách nhau một ký tự trắng: N là số ô vuông (2 ≤ N ≤ 10⁵), K là số ô vuông tối đa bạn học sinh có thể nhảy qua (1 ≤ K ≤ 100).
• Dòng thứ hai chứa N giá trị hᵢ (1 ≤ hᵢ ≤ 10⁴), mỗi số cách nhau một ký tự trắng là chi phí năng lượng của ô vuông thứ i tương ứng.

Lưu ý: Các giá trị là số nguyên.

Kết quả: ghi ra file GAME.OUT một số là tổng chi phí phát sinh tối thiểu.

Ví dụ:

GAME.INP	GAME.OUT
5 3 10 25 35 40 20	20

Giải thích: Cách nhảy của bạn học sinh sẽ là: 1 → 2 → 5, tổng chi phí phát sinh sẽ là |25 − 10| + |20 − 25| = 20.