HSG THPT Tiền Giang 2023-2024

SỞ GIÁO DỤC VÀ ĐÀO TẠO TỈNH TIỀN GIANG ĐỀ THI CHÍNH THỨC
(Đề thi có 03 trang)

KỲ THI CHỌN HỌC SINH GIỎI CẤP TỈNH TRUNG HỌC PHỔ THÔNG Năm học 2023-2024
Môn thi: Tin học
Thời gian làm bài: 180 phút, không kể thời gian phát đề
Ngày thi: 27/02/2024

---

Tổng quan các bài thi

	Tên bài	File chương trình	File dữ liệu vào	File kết quả
Bài 1	Ước nguyên tố	PRIME.*	PRIME.INP	PRIME.OUT
Bài 2	Dãy con đặc biệt	EXLIST.*	EXLIST.INP	EXLIST.OUT
Bài 3	Con kiến	ANT.*	ANT.INP	ANT.OUT

Dấu * được thay thế bởi PAS, CPP, PY của ngôn ngữ lập trình được sử dụng tương ứng là Pascal, C++ hoặc Python.

Mỗi thí sinh được phép chọn duy nhất một ngôn ngữ lập trình để giải các bài toán sau:

Bài 1. Ước nguyên tố (6,0 điểm)

Số nguyên tố là số nguyên dương lớn hơn 1 chỉ có hai ước số là 1 và chính nó. Với mọi số tự nhiên X (với X > 1) đều có ít nhất một ước số nguyên tố.

Ví dụ: X = 4 có một ước nguyên tố là 2.

X = 6 có hai ước nguyên tố là 2 và 3.

Yêu cầu: Cho dãy số a gồm n số nguyên dương: a₁, a₂, …, a_n. Hãy cho biết trong dãy số trên, số nào có nhiều ước số nguyên tố nhất? Nếu có nhiều đáp án thì ghi ra số có thứ tự trong dãy nhỏ nhất thỏa mãn yêu cầu.

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

• Dòng 1: Chứa một số nguyên dương n là số lượng các phần tử của dãy a (với 2 ≤ n ≤ 10⁶)
• Dòng 2: Chứa n số nguyên dương a_i (2 ≤ a_i ≤ 10⁶, 1 ≤ i ≤ n), mỗi số cách nhau bởi một dấu cách.

Kết quả ra: Ghi ra tệp văn bản PRIME.OUT gồm duy nhất một số nguyên thỏa mãn yêu cầu bài toán.

Ràng buộc:

• Các test tương ứng với 40% số điểm có: 2 ≤ n ≤ 10² và 2 ≤ a_i ≤ 10³.
• Các test tương ứng với 40% số điểm có: 10² < n ≤ 10⁵ và 10³ < a_i ≤ 10⁵.
• Các test tương ứng với 20% số điểm: Không có ràng buộc gì thêm.

Ví dụ:

PRIME.INP	PRIME.OUT
6 2 10 6 4 8 15	10

Bài 2. Đoạn con đặc biệt (7,0 điểm)

Cho một dãy số nguyên dương gồm n phần tử: a₁, a₂, …, a_n. Một đoạn [L, R] của dãy a là một dãy con có các phần tử liên tiếp a_L, a_(L+1), …, a_R với 1 ≤ L ≤ R ≤ n. Hãy tìm một đoạn con đặc biệt của dãy a? Biết đoạn [L, R] được gọi là đoạn con đặc biệt nếu:

• Phần tử đầu bằng phần tử cuối (a_L = a_R)
• Độ dài đoạn con dài nhất.
• Tổng các phần tử của đoạn con là lớn nhất có thể.

Yêu cầu: Tìm độ dài đoạn con đặc biệt và tính tổng các phần tử trong đoạn con đó?

Dữ liệu vào: Đọc từ tệp văn bản EXLIST.INP gồm:

• Dòng 1: Chứa một số nguyên dương n là số lượng phần tử của dãy a (với 2 ≤ n ≤ 10⁶);
• Dòng 2: Chứa n số nguyên a₁, a₂, …, a_n (0 < a_i ≤ 10³; 1 ≤ i ≤ n), mỗi số cách nhau bởi một dấu cách.

Kết quả ra: Ghi ra tệp văn bản EXLIST.OUT hai số nguyên là độ dài và tổng các phần tử trong đoạn con đặc biệt tìm được, hai số cách nhau bởi một dấu cách.

Ràng buộc:

• Các test tương ứng với 40% số điểm có: 2 ≤ n ≤ 10².
• Các test tương ứng với 40% số điểm có: 10² < n ≤ 10³.
• Các test tương ứng với 20% số điểm: Không có ràng buộc gì thêm.

Ví dụ:

EXLIST.INP	EXLIST.OUT	Giải thích
10 1 2 8 8 2 7 5 4 7 5	4 23	Đoạn con đặc biệt là: [7, 5, 4, 7] → Độ dài là 4, tổng là 23
9 1 2 1 3 1 4 7 9 4	5 8	Đoạn con đặc biệt là: [1, 2, 1, 3, 1] → Độ dài là 5, tổng là 8

Bài 3. Con kiến (7,0 điểm)

Khu vực sinh sống của một con kiến là một ma trận hình chữ nhật kích thước n × m ô. Mỗi ô của ma trận có thể là ô trống được kí hiệu bởi kí tự ‘1’ hoặc có thể là ô cấm kí hiệu bởi kí tự ‘0’. Con kiến đang ở tại ô (1, 1) của ma trận. Nó cần tìm con đường di chuyển với số bước ít nhất đến ô (n, m) để lấy thức ăn. Theo bạn, con kiến có bao nhiêu đường đi như thế để di chuyển đến ô (n, m) và số bước ít nhất là bao nhiêu? Biết rằng, mỗi bước di chuyển từ ô (i, j), kiến có thể đi tới 4 ô chung cạnh không phải là ô cấm và tất nhiên kiến không được đi ra ngoài ma trận.

Dữ liệu vào: Đọc từ tệp văn bản ANT.INP gồm:

• Dòng đầu tiên chứa hai số nguyên n, m (2 ≤ n, m ≤ 10³) lần lượt là số dòng, số cột của ma trận.
• n dòng tiếp theo: dòng thứ i chứa một xâu độ dài m gồm hai loại kí tự ‘1’ hoặc ‘0’ mô tả dòng thứ i của ma trận.
• Dữ liệu vào đảm bảo con kiến luôn tìm được đường đi lấy thức ăn.

Kết quả ra: Ghi vào tệp văn bản ANT.OUT gồm:

• Dòng 1: Ghi một số nguyên là phần dư của số đường đi cần tìm chia cho 10⁸ + 7.
• Dòng 2: Ghi một số nguyên là số bước ít nhất mà kiến phải đi để lấy thức ăn.

Ràng buộc:

• Các test tương ứng với 20% số điểm có: 2 ≤ n × m ≤ 10.
• Các test tương ứng với 40% số điểm có: 2 ≤ n, m ≤ 10².
• Các test tương ứng với 40% số điểm: Không có ràng buộc gì thêm.

Ví dụ:

ANT.INP	ANT.OUT	Giải thích
3 3 101 111 011	2 4	Có 2 đường đi từ ô (1,1) đến ô (3,3) với số bước ít nhất (4 bước)
2 2 11 01	1 2	Có 1 đường đi từ ô (1,1) đến ô (2,2) với số bước ít nhất (2 bước)

---

Thí sinh không được sử dụng tài liệu. Giám thị không giải thích gì thêm.