HSG THCS Quảng Ninh 2025-2026

SỞ GIÁO DỤC VÀ ĐÀO TẠO TỈNH QUẢNG NINH ĐỀ THI CHÍNH THỨC

KỲ THI CHỌN HỌC SINH GIỎI CẤP TỈNH THCS NĂM 2026 Môn thi: Tin học - Ngày thi: 22/01/2026
Thời gian làm bài: 150 phút, không kể thời gian giao đề
(Đề thi này có 04 trang)

---

Tổng quan bài thi

Bài	Tên bài	Tệp chương trình	Tệp dữ liệu	Tệp kết quả	Bộ nhớ	Thời gian / test	Điểm
1	Tiền công	sal.*	sal.inp	sal.out	1024 MB	1 giây	6,0 điểm
2	Giá trị	val.*	val.inp	val.out	1024 MB	1 giây	6,0 điểm
3	Dãy số	arr.*	arr.inp	arr.out	1024 MB	1 giây	5,0 điểm
4	Số cặp	pai.*	pai.inp	pai.out	1024 MB	2 giây	3,0 điểm

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

Hãy lập trình giải các bài toán sau:

Bài 1. Tiền công (6,0 điểm)

Một công nhân tham gia một đợt làm thêm kéo dài liên tiếp trong d ngày. Ngày bắt đầu của đợt làm thêm này là ngày thứ k trong tuần. Tiền công làm việc hàng ngày được quy định như sau:

• Các ngày từ thứ Hai đến thứ Sáu: Tiền công là a đồng mỗi ngày;
• Các ngày thứ Bảy và Chủ Nhật: Tiền công là b đồng mỗi ngày.

Yêu cầu: Cho biết các giá trị k, d, a và b, hãy tính tổng số tiền công mà người công nhân đó nhận được sau khi kết thúc d ngày làm việc.

Dữ liệu vào: từ tệp văn bản sal.inp gồm một dòng duy nhất chứa 4 số nguyên k, d, a, b:

• k là thứ bắt đầu (2 ≤ k ≤ 8, trong đó 2 là thứ Hai, 3 là thứ Ba, …, 8 là Chủ Nhật);
• d là tổng số ngày làm việc (1 ≤ d ≤ 1000);
• a, b là tiền công tương ứng (1 ≤ a, b ≤ 10⁵).

Kết quả: ghi ra tệp văn bản sal.out một dòng duy nhất chứa một số nguyên là tổng số tiền công nhận được.

Các số trên một dòng của dữ liệu vào được ghi cách nhau bởi một dấu cách.

Ví dụ:

sal.inp	sal.out
2 4 3 5	12
2 7 2 4	18
4 14 2 3	32
3 12 1 2	15

Ràng buộc:

• Ràng buộc 1: 80% số test ứng với 80% số điểm của bài có 1 ≤ d ≤ 5, k = 2;
• Ràng buộc 2: 20% số test ứng với 20% số điểm của bài có 6 ≤ d ≤ 1000.

Giải thích test 1: k = 2, d = 4, a = 3, b = 5 tức là công nhân bắt đầu làm từ thứ Hai và d = 4 nên sẽ làm liên tiếp các ngày thứ Hai, Ba, Tư và thứ Năm. Vì vậy tiền công là d * a = 4 * 3 = 12.

Bài 2. Giá trị (6,0 điểm)

Cho dãy một gồm n số nguyên a₁, a₂, …, aₙ. Một dãy con liên tiếp là dãy có dạng aᵢ, aᵢ₊₁, …, aⱼ (1 ≤ i ≤ j ≤ n), j − i + 1 được gọi là độ dài của dãy con đó.

Yêu cầu: Hãy tìm độ dài lớn nhất của dãy con liên tiếp chỉ bao gồm đúng k giá trị.

Dữ liệu vào: từ file văn bản val.inp

• Dòng đầu chứa hai số nguyên n, k (2 ≤ n ≤ 10⁵; 1 ≤ k ≤ 2);
• Dòng thứ hai chứa n số nguyên a₁, a₂, …, aₙ (1 ≤ aᵢ ≤ 3; i = 1, 2, …, n).

Kết quả: ghi ra file văn bản val.out một số nguyên duy nhất là độ dài lớn nhất của dãy con liên tiếp chỉ bao gồm đúng k giá trị.

Các số trên một dòng của dữ liệu vào được ghi cách nhau bởi một dấu cách. Dữ liệu đầu vào đảm bảo bài toán luôn tồn tại đáp án.

Ví dụ:

val.inp	val.out	Giải thích
8 1 1 1 1 2 2 2 2 2	5	Dãy con thỏa mãn: 2 2 2 2 2
10 1 1 2 2 3 2 3 3 3 1 1	3	Dãy con thỏa mãn: 3 3 3
10 2 1 3 2 3 3 1 1 3 1 2	6	Dãy con thỏa mãn: 3 3 1 1 3 1

Ràng buộc:

• Ràng buộc 1: 40% số test ứng với 40% số điểm của bài có k = 1; 1 ≤ aᵢ ≤ 2 với mọi i = 1, 2, …, n và aᵢ ≤ aᵢ₊₁ với mọi i = 1, 2, …, n − 1;
• Ràng buộc 2: 40% số test ứng với 40% số điểm của bài có k = 1;
• Ràng buộc 3: 20% số test ứng với 20% số điểm của bài có k = 2.

Bài 3. Dãy số (5,0 điểm)

Cho một dãy gồm n số nguyên a₁, a₂, …, aₙ và các số nguyên b, k₁, k₂. Bạn được thực hiện tối đa k₁ + k₂ phép toán trên các phần tử của dãy để giảm tổng các phần tử của dãy số đã cho.

• Phép toán loại 1: Chọn một số aᵢ bất kì của dãy và thay thế số aᵢ bằng số ⌊aᵢ/2⌋ (chia đôi và lấy phần nguyên, ví dụ: ⌊17/2⌋ = 8). Bạn được sử dụng tối đa k₁ phép toán loại 1.
• Phép toán loại 2: Chọn một số aᵢ bất kì của dãy và thay thế aᵢ bằng giá trị lớn nhất của hai số aᵢ − b và 0 (trừ đi b đơn vị, nếu kết quả âm thì lấy bằng 0). Bạn được sử dụng tối đa k₂ phép toán loại 2.

Quy tắc: Với mỗi số aᵢ trong dãy, bạn có thể chọn: không phép toán nào, chỉ phép toán loại 1, chỉ phép toán loại 2, hoặc dùng cả hai phép toán, mỗi phép toán được thực hiện tối đa 1 lần với số aᵢ. Nếu dùng cả hai loại trên cùng một số, bạn có thể thực hiện theo thứ tự nào tùy ý.

Yêu cầu: Hãy tìm tổng nhỏ nhất của dãy số sau khi sử dụng tối đa k₁ phép toán loại 1 và k₂ phép toán loại 2.

Dữ liệu vào: từ tệp văn bản arr.inp

• Dòng đầu chứa 4 số nguyên n, b, k₁, k₂ (1 ≤ n ≤ 300, 1 ≤ b ≤ 10⁹, 0 ≤ k₁, k₂ ≤ n);
• Dòng thứ hai chứa n số nguyên dương aᵢ (1 ≤ aᵢ ≤ 10⁹).

Dữ liệu ra: ghi ra tệp văn bản arr.out

• Một số nguyên duy nhất là tổng nhỏ nhất tìm được.

Các số trên một dòng của dữ liệu vào được ghi cách nhau bởi một dấu cách.

Ví dụ:

arr.inp	arr.out
7 4 2 0 1 2 1 8 3 5 7	19
7 4 2 1 1 2 1 8 3 5 7	15
7 9 4 5 19 2 1 8 8 5 5	1
7 9 4 4 8 8 8 8 8 8 8	12

Giải thích test 3: Thực hiện phép toán loại 1 với a₁ thì a₁ = ⌊19/2⌋ = 9. Tiếp theo thực hiện 5 phép toán loại 2 với các phần tử a₁, a₄, a₅, a₆, a₇ ta được dãy mới: 0, 2, 1, 0, 0, 0, 0. Sau đó thực hiện 3 phép toán loại 1 với các phần tử a₂, a₃, a₄ ta được dãy mới: 0, 1, 0, 0, 0, 0, 0 có tổng bằng 1.

Ràng buộc:

• Ràng buộc 1: 30% số test ứng với 30% số điểm của bài có k₂ = 0;
• Ràng buộc 2: 30% số test ứng với 30% số điểm của bài có a₁ = a₂ = ⋯ = aₙ;
• Ràng buộc 3: 40% số test ứng với 40% số điểm của bài có n, k₁, k₂ ≤ 300, các giá trị đầu vào khác không có ràng buộc gì thêm.

Bài 4. Số cặp (3,0 điểm)

Cho hai dãy gồm n số nguyên, dãy thứ nhất gồm các số a₁, a₂, …, aₙ, dãy thứ hai gồm các số b₁, b₂, …, bₙ.

Yêu cầu: Hãy đếm số cặp chỉ số (i, j) (1 ≤ i ≤ j ≤ n) mà số lớn nhất của các số aᵢ, aᵢ₊₁, …, aⱼ bằng số nhỏ nhất của các số bᵢ, bᵢ₊₁, …, bⱼ.

Dữ liệu vào: từ tệp văn bản pai.inp

• Dòng đầu tiên chứa số nguyên n (1 ≤ n ≤ 10⁵);
• Dòng thứ hai chứa n số nguyên a₁, a₂, …, aₙ (1 ≤ |aᵢ| ≤ 10⁹);
• Dòng thứ ba chứa n số nguyên b₁, b₂, …, bₙ (1 ≤ |bᵢ| ≤ 10⁹).

Kết quả: ghi ra tệp văn bản pai.out

• Một dòng duy nhất là kết quả của bài toán.

Các số trên một dòng của dữ liệu vào được ghi cách nhau bởi một dấu cách.

Ví dụ:

pai.inp	pai.out
6 1 2 3 2 1 4 6 7 1 2 3 2	2
3 3 3 3 3 3 3	6
7 1 2 3 4 8 8 9 2 4 6 8 8 8 9	8
10 1 2 3 2 1 3 2 1 2 1 6 7 1 2 3 2 2 3 1 2	4

Ràng buộc:

• Ràng buộc 1: 25% số test ứng với 25% số điểm của bài có n ≤ 100;
• Ràng buộc 2: 25% số test ứng với 25% số điểm của bài có n ≤ 5000;
• Ràng buộc 3: 25% số test ứng với 25% số điểm của bài có n ≤ 10⁵, a₁ ≤ a₂ ≤ ⋯ ≤ aₙ, b₁ ≤ b₂ ≤ ⋯ ≤ bₙ;
• Ràng buộc 4: 25% số test còn lại ứng với 25% số điểm của bài không có ràng buộc gì thêm.

---

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