HSG lớp 11 Quảng Bình 2023-2024

SỞ GD&ĐT QUẢNG BÌNH ĐỀ CHÍNH THỨC
(Đề gồm có 02 trang và 03 câu)

KỲ THI CHỌN HSG LỚP 11 NĂM HỌC 2023-2024 VÀ CHỌN ĐỘI DỰ TUYỂN DỰ THI CHỌN HSG QUỐC GIA NĂM HỌC 2024-2025 Khóa ngày 02 tháng 4 năm 2024
Môn thi: Tin học - Bài thi thứ nhất
Thời gian: 180 phút (không kể thời gian giao đề)

---

Ghi chú

Trang này có đề bài thi thứ nhất. Đề bài thi thứ hai đang được cập nhật.

Sử dụng ngôn ngữ lập trình Pascal, C, C++, Python để giải quyết các bài toán sau:

Câu	Tên file bài làm	Tên file dữ liệu vào	Tên file dữ liệu ra	Điểm số
1	ASTRING.*	ASTRING.INP	ASTRING.OUT	3.0
2	GAME.*	GAME.INP	GAME.OUT	3.5
3	PRIME.*	PRIME.INP	PRIME.OUT	3.5

Câu 1: (3.0 điểm) Xâu con

Cho hai xâu ký tự s1, s2, các ký tự trong hai xâu được lấy trong tập ‘A’… ‘Z’. Xâu s1 được gọi là xâu con của xâu s2 nếu xóa đi một số ký tự trong xâu s2 thì ta được xâu s1.

Ví dụ: xâu ‘ABC’ là một xâu con của xâu ‘CDACDBDDCA’

Yêu cầu: Với hai xâu cho trước, hãy xác định xem xâu s1 có phải là xâu con của xâu s2 hay không?

Dữ liệu vào: Cho trong file ASTRING.INP có cấu trúc như sau:

• Dòng 1: Ghi hai số nguyên dương M, N tương ứng là độ dài của xâu s1 và độ dài của xâu s2. Các số được ghi cách nhau ít nhất một dấu cách. (0 < M ≤ N ≤ 3.10⁴).
• Dòng 2: Ghi xâu ký tự s1.
• Dòng 3: Ghi xâu ký tự s2.

Dữ liệu ra: Ghi ra file ASTRING.OUT với cấu trúc như sau:

• Dòng 1: Ghi ký tự ‘Y’ nếu xâu s1 là xâu con của xâu s2, ngược lại ghi ký tự ‘N’.

Ví dụ:

ASTRING.INP	ASTRING.OUT
3 10 ABC CDACDBDDCA	Y
3 10 ABC CBDACBDDDA	N

Câu 2: (3.5 điểm) Trò chơi

Nhân dịp kỷ niệm ngày thành lập Đoàn thanh niên Cộng sản Hồ Chí Minh, nhằm khơi dậy niềm đam mê học tập, sáng tạo của đoàn viên thanh niên, Đoàn trường X tổ chức trò chơi có thưởng như sau: Cho N phần quà được đánh số từ 1 đến N, phần quà thứ i có giá trị là A_i. Giải thưởng là phần quà có giá trị bằng số nguyên dương S = 2A_i − A_j − A_k (0 < i < j < k ≤ N).

Yêu cầu: Hãy giúp các đoàn viên trường X tìm được giải thưởng có giá trị lớn nhất.

Dữ liệu vào: Cho trong file GAME.INP có cấu trúc như sau:

• Dòng 1: Ghi số nguyên dương N (0 < N ≤ 10⁶).
• Dòng 2: Ghi N số nguyên dương A₁, A₂, … A_N lần lượt là giá trị của N phần quà. (0 < A_i ≤ 10⁶; 0 < i ≤ N)

Dữ liệu ra: Ghi ra file GAME.OUT với cấu trúc như sau:

• Dòng 1: Ghi số nguyên dương S là giá trị của giải thưởng tìm được. Nếu không tìm được S dương thì ghi số 0.

Ví dụ:

GAME.INP	GAME.OUT
6 1 20 2 21 7 4	34
6 1 2 7 4 21 20	0

Câu 3: (3.5 điểm) Phân tích nguyên tố

Số nguyên dương M được gọi là số nguyên tố toàn diện nếu thỏa mãn đồng thời hai điều kiện sau:

• M là số nguyên tố.
• Khi lần lượt bỏ đi một chữ số sau cùng của M thì thu được một số nguyên dương cũng là số nguyên tố.

Ví dụ: Số M = 7331 là số nguyên tố toàn diện vì:

• 7331 là số nguyên tố.
• 733 là số nguyên tố.
• 73 là số nguyên tố.
• 7 là số nguyên tố.

Số K được gọi là số gần nguyên tố toàn diện nếu K là số nguyên tố toàn diện hoặc tồn tại một cách phân tích K thành tổng các số nguyên tố toàn diện mà trong cách phân tích đó mỗi số nguyên tố toàn diện chỉ xuất hiện nhiều nhất một lần.

Yêu cầu: Cho số nguyên dương N, hãy liệt kê các số gần nguyên tố toàn diện trong phạm vi từ 2 đến N.

Dữ liệu vào: Cho trong file PRIME.INP có cấu trúc như sau:

• Dòng 1: Ghi số nguyên dương N. (0 < N ≤ 5.10⁶)

Dữ liệu ra: Ghi ra file PRIME.OUT với cấu trúc như sau:

• Dòng 1: Ghi các số gần nguyên tố toàn diện tìm được theo thứ tự tăng dần. Các số được ghi cách nhau một dấu cách.

Ví dụ:

PRIME.INP	PRIME.OUT
8	2 3 5 7 8

Giải thích: Số 8 là số gần nguyên tố toàn diện vì: 8 = 3 + 5