HSG THCS Quảng Nam 2024-2025

SỞ GIÁO DỤC VÀ ĐÀO TẠO TỈNH QUẢNG NAM ĐỀ CHÍNH THỨC
(Đề thi gồm có 03 trang)

KỲ THI CHỌN HỌC SINH GIỎI CẤP TỈNH THCS Năm học 2024 - 2025
Môn thi: Tin học - Ngày thi: 04/4/2025
Thời gian: 150 phút (không kể thời gian giao đề)

---

Tổng quan đề thi

Câu	Tên câu	Tên file chương trình	Dữ liệu vào	Dữ liệu ra	Thời gian
1	Đếm các cặp số	CAU1.*	CAU1.INP	CAU1.OUT	1.0 giây
2	Ghép giày	CAU2.*	CAU2.INP	CAU2.OUT	0.4 giây
3	Doanh thu lớn nhất	CAU3.*	CAU3.INP	CAU3.OUT	0.3 giây
4	Bảng số	CAU4.*	CAU4.INP	CAU4.OUT	0.5 giây

• Dấu * được thay thế bởi C, CPP hoặc PY của ngôn ngữ lập trình được sử dụng tương ứng là C, C++ hoặc Python.
• Trong file dữ liệu vào ra, các số trên cùng một hàng được ghi cách nhau một dấu cách.

Câu 1. Đếm các cặp số (5.0 điểm)

Cho ba số nguyên dương n, A và B (1 ≤ n, A, B ≤ 2 × 10⁶).

Yêu cầu: Đếm số lượng cặp số (x, y) thỏa mãn 1 ≤ x < y ≤ n và A ≤ x + y ≤ B.

Dữ liệu vào: Từ file văn bản CAU1.INP ghi lần lượt các số là n, A và B (A ≤ B).

Kết quả: Ghi ra file văn bản CAU1.OUT một số duy nhất là số lượng cặp số tìm được.

Ví dụ:

CAU1.INP	CAU1.OUT
5 6 9	6
2024 2025 2025	1012

Ràng buộc:

• Có 70% số điểm: 1 ≤ n ≤ 2000;
• Có 20% số điểm: 2000 < n ≤ 10⁵ và A = B;
• Có 10% số điểm còn lại không có ràng buộc gì thêm.

Câu 2. Ghép giày (5.0 điểm)

Công ty giày thời trang vừa nhập về kho N chiếc giày từ nhà máy, thông tin mỗi chiếc giày là một xâu gồm 4 kí tự có ý nghĩa như sau:

• Kí tự đầu tiên là L hoặc R tương ứng với chiếc giày đó bên trái hoặc bên phải;
• Kí tự thứ hai là R hoặc B tương ứng với chiếc giày đó màu đỏ hoặc màu xanh;
• Hai kí tự số cuối cùng cho biết kích cỡ của chiếc giày.

Ví dụ xâu LB42 cho biết chiếc giày này là bên trái, màu xanh và kích cỡ là 42. Xâu RR30 cho biết chiếc giày này là bên phải, màu đỏ và kích cỡ là 30.

Hai chiếc giày bên trái và bên phải được ghép thành một đôi khi chúng có cùng kích cỡ nhưng màu sắc khác nhau. Mỗi chiếc giày chỉ thuộc tối đa một đôi giày.

Dữ liệu vào: Từ file văn bản CAU2.INP gồm:

• Dòng thứ nhất chứa duy nhất số nguyên dương N (1 ≤ N ≤ 10⁶);
• Trong N dòng tiếp theo, mỗi dòng ghi một xâu kí tự biểu diễn thông tin một chiếc giày.

Kết quả: Ghi ra file văn bản CAU2.OUT một số duy nhất là số lượng đôi giày ghép được.

Ví dụ:

CAU2.INP	CAU2.OUT	Giải thích
5 RB30 LB30 RB30 LB42 LR30	1	Ghép được LR30 với RB30 thành một đôi.

Ràng buộc:

• Có 60% số điểm: 1 ≤ N ≤ 1000;
• Có 20% số điểm: 1000 < N < 10⁵;
• Có 20% số điểm: 10⁵ < N ≤ 10⁶.

Câu 3. Doanh thu (5.0 điểm)

Doanh thu của một công ty trong N ngày tiếp theo (các ngày được đánh số từ 1 đến N, 1 < N ≤ 10⁵) dự kiến lần lượt là A₁, A₂, …, A_N (|Aᵢ| ≤ 10⁹). Hội đồng quản trị của công ty muốn chọn ra ít nhất K ngày liên tiếp nhau (1 ≤ K < N) sao cho tổng doanh thu trong những ngày được chọn là lớn nhất.

Yêu cầu: Tính tổng doanh thu lớn nhất mà hội đồng quản trị có thể chọn được.

Dữ liệu vào: Từ file văn bản CAU3.INP gồm:

• Dòng thứ nhất chứa hai số nguyên dương N và K;
• Dòng thứ hai ghi N số nguyên A₁, A₂, …, A_N.

Kết quả: Ghi ra file văn bản CAU3.OUT một số duy nhất là tổng doanh thu lớn nhất chọn được.

Ví dụ:

CAU3.INP	CAU3.OUT	Giải thích
5 2 1 2 3 4 -5	10	Chọn 4 ngày có doanh thu lần lượt: 1, 2, 3 và 4.
6 2 1 -2 3 -4 5 -1	4	Chọn 3 ngày có doanh thu lần lượt: 3, -4 và 5.

Ràng buộc:

• Có 40% số điểm: 1 < N ≤ 200;
• Có 30% số điểm: 200 < N ≤ 2000;
• Có 30% số điểm còn lại không có ràng buộc gì thêm.

Câu 4. Bảng số (5.0 điểm)

Cho dãy số nguyên A gồm N phần tử có giá trị lần lượt A₁, A₂, …, A_N. Bảng số B gồm N hàng và N cột, các hàng và cột đều được đánh số từ 1 đến N theo thứ tự từ trên xuống dưới và từ trái sang phải, giá trị tại ô ở hàng i và cột j của bảng B là Bᵢⱼ = Aᵢ × Aⱼ (1 ≤ i, j ≤ N).

Ví dụ với A = (1, 5, 3, 2) thì B là:

1	5	3	2
5	25	15	10
3	15	9	6
2	10	6	4

Khi đặt quân xe ở ô (i, j) trên bảng thì tất cả các ô trên hàng i và cột j đều bị quân xe khống chế, ngoại trừ ô nó đang đứng.

Yêu cầu: Cho biết vị trí đặt quân xe, tính tổng giá trị các ô trên bảng B bị quân xe khống chế.

Dữ liệu vào: Từ file văn bản CAU4.INP gồm:

• Dòng thứ nhất ghi số nguyên dương N (1 ≤ N ≤ 10³);
• Dòng thứ hai ghi N số nguyên A₁, A₂, …, A_N (1 ≤ Aᵢ ≤ 10⁴);
• Dòng thứ ba ghi số nguyên dương M (1 ≤ M ≤ 2 × 10⁵) là số lần đặt quân xe;
• Dòng thứ i trong M dòng tiếp theo, mỗi dòng ghi hai số nguyên xᵢ và yᵢ là chỉ số hàng và chỉ số cột của ô đặt quân xe ở lần thứ i (1 ≤ i ≤ M, 1 ≤ xᵢ, yᵢ ≤ N).

Kết quả: Ghi ra file văn bản CAU4.OUT gồm M dòng, mỗi dòng ghi một tổng tương ứng với vị trí đặt quân xe.

Ví dụ:

CAU4.INP	CAU4.OUT
4 1 5 3 2 2 2 3 3 1	58 38

Ràng buộc:

• Có 60% số điểm: 1 ≤ N, M ≤ 100;
• Có 40% số điểm còn lại không có ràng buộc gì thêm.

---

Hết