HSG THCS Hải Phòng 2025-2026

SỞ GIÁO DỤC VÀ ĐÀO TẠO THÀNH PHỐ HẢI PHÒNG ĐỀ CHÍNH THỨC
(Đề thi gồm 05 bài; 04 trang)

KỲ THI CHỌN HỌC SINH GIỎI THÀNH PHỐ Cấp THCS năm học 2025 - 2026
Môn thi: Tin học
Thời gian làm bài: 150 phút

Tổng quan đề thi

Đối với các thí sinh sử dụng ngôn ngữ C++:

	Tên file nguồn nộp	Dữ liệu nhập từ	Kết quả in ra	Giới hạn bộ nhớ	Điểm
Bài 1	`CBAI1.CPP`	Bàn phím	Màn hình	1024 MB	5,0
Bài 2	`CBAI2.CPP`	Bàn phím	Màn hình	1024 MB	5,0
Bài 3	`CBAI3.CPP`	Bàn phím	Màn hình	1024 MB	6,0
Bài 4	`CBAI4.CPP`	Bàn phím	Màn hình	1024 MB	6,0
Bài 5	`CBAI5.CPP`	Bàn phím	Màn hình	1025 MB	8,0

Đối với các thí sinh sử dụng ngôn ngữ Python:

	Tên file nguồn nộp	Dữ liệu nhập từ	Kết quả in ra	Giới hạn bộ nhớ	Điểm
Bài 1	`PBAI1.PY`	Bàn phím	Màn hình	1024 MB	5,0
Bài 2	`PBAI2.PY`	Bàn phím	Màn hình	1024 MB	5,0
Bài 3	`PBAI3.PY`	Bàn phím	Màn hình	1024 MB	6,0
Bài 4	`PBAI4.PY`	Bàn phím	Màn hình	1024 MB	6,0
Bài 5	`PBAI5.PY`	Bàn phím	Màn hình	1025 MB	8,0

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

Bài 1 (5 điểm)

Một số nguyên dương x được gọi là đẹp nếu như nó chia hết cho 5 và tổng các chữ số của nó cũng chia hết cho 5.

Yêu cầu: Cho dãy n số nguyên dương a₁, a₂, …, a_n. Hãy đếm xem có bao nhiêu số đẹp trong dãy trên.

Dữ liệu: Nhập từ bàn phím

Dòng đầu chứa số nguyên dương n
Tiếp theo là n dòng, dòng thứ i (i = 1, 2, …, n) chứa số nguyên dương a_i. Tổng số lượng các chữ số của a₁, a₂, …, a_n không vượt quá 10⁶

Kết quả: In ra màn hình một số nguyên duy nhất là số lượng số đẹp trong dãy số đã cho.

Ràng buộc:

Có 80% số tests ứng với 80% số điểm của bài thoả mãn a_i ≤ 10⁹ ∀i = 1, 2, …, n
Các tests còn lại không có ràng buộc bổ sung

Ví dụ:

Dữ liệu	Kết quả
`5` `15` `50` `140` `25` `10`	`2`

Giải thích: Chỉ có 2 số 50, 140 thoả mãn đồng thời hai điều kiện: chia hết cho 5 và tổng các chữ số cũng chia hết cho 5.

Bài 2 (5 điểm)

Sau n bài kiểm tra, điểm của Dũng được ghi lại thành dãy số nguyên a₁, a₂, …, a_n. Điểm này có thể âm (tương ứng với điểm phạt) nếu như lần kiểm tra đó Dũng gian lận hoặc sử dụng chat GPT. Thầy giáo muốn biết “giai đoạn tiến bộ nhất” mà Dũng thực hiện được, giai đoạn này là dãy các bài kiểm tra liên tiếp của Dũng có tổng điểm lớn nhất.

Yêu cầu: Hãy xác định tổng điểm của “giai đoạn tiến bộ nhất” mà Dũng thực hiện được.

Dữ liệu: Nhập từ bàn phím

Dòng đầu tiên chứa số nguyên dương n (1 ≤ n ≤ 10⁶)
Dòng thứ hai chứa n số nguyên lần lượt là a₁, a₂, …, a_n (|a_i| ≤ 10⁹ ∀i = 1, 2, …, n). Hai số liên tiếp cách nhau bằng khoảng trống (space)

Kết quả: In ra màn hình một số nguyên duy nhất là kết quả tìm được.

Ràng buộc:

Có 50% số tests ứng với 50% số điểm của bài có n ≤ 500
30% số tests tiếp theo ứng với 30% số điểm của bài có n ≤ 5000
Các tests còn lại không có ràng buộc bổ sung

Ví dụ:

Dữ liệu	Kết quả
`9` `-90 1 3 -2 5 -1 2 5 -3`	`13`

Giải thích: Dãy điểm cần tìm là 1, 3, −2, 5, −1, 2, 5 có tổng 1 + 3 − 2 + 5 − 1 + 2 + 5 = 13

Bài 3 (6 điểm)

Cho dãy n số nguyên a₁, a₂, …, a_n và số nguyên dương M. Hãy đếm số lượng cặp (i, j) với 1 ≤ i < j ≤ n sao cho a_i + a_j chia hết cho M.

Dữ liệu: Nhập từ bàn phím

Dòng đầu chứa hai số nguyên dương n, M (n ≤ 3 × 10⁵; M ≤ 10¹⁸)
Dòng thứ hai chứa n số nguyên lần lượt là a₁, a₂, …, a_n (|a_i| ≤ 10¹⁸ ∀i = 1, 2, …, n)

Hai số liên tiếp trên cùng một dòng cách nhau bằng khoảng trống (space)

Kết quả: Ghi ra màn hình một số nguyên duy nhất là số cặp tìm được.

Ràng buộc:

Có 40% số tests ứng với 40% số điểm của bài có n ≤ 5000
20% số tests tiếp theo ứng với 20% số điểm của bài có M ≤ 10⁶
Các tests còn lại không có ràng buộc bổ sung

Ví dụ:

Dữ liệu	Kết quả
`5 4` `1 3 2 6 2`	`4`

Giải thích: Các cặp (i, j) tìm được là (1,2), (3,4), (3,5), (4,5).

Bài 4 (6 điểm)

Trước cửa nhà Dũng có n cây hoa hồng trồng thành một dãy và đánh số 1, 2, …, n từ trái qua phải. Dũng đánh giá “độ đẹp” của những bông hoa hồng trong cây hoa hồng thứ i bằng một số nguyên dương a_i. Nhân ngày Quốc tế Phụ nữ (8/3), Dũng muốn làm 2 bó hoa tặng mẹ và tặng cô giáo chủ nhiệm bằng cách chọn mỗi cây hoa hồng không quá một bông hoa. Một bó hoa được gọi là đẹp nếu như “độ đẹp” của các bông hoa hồng trong bó hoa này chênh lệch nhau không quá K. Tất nhiên Dũng muốn tổng số bông hồng trong cả hai bó hoa càng lớn càng tốt.

Yêu cầu: Hãy tìm số lượng bông hồng lớn nhất có thể được chọn để làm 2 bó hoa.

Dữ liệu: Nhập từ bàn phím

Dòng đầu tiên chứa hai số nguyên dương n, K (n ≤ 10⁶; K ≤ 10⁹)
Dòng thứ hai chứa n số nguyên dương lần lượt là a₁, a₂, …, a_n (a_i ≤ 10⁹)

Hai số liên tiếp trên cùng một dòng cách nhau bằng khoảng trống (space)

Kết quả: Ghi ra màn hình một số nguyên duy nhất là tổng số lượng bông hoa tối đa trong hai bó hoa.

Ràng buộc:

Có 30% số tests ứng với 30% số điểm của bài có n ≤ 10
20% số tests tiếp theo ứng với 20% số điểm của bài có n ≤ 100
20% số tests tiếp theo ứng với 20% số điểm của bài có n ≤ 5000
Các tests còn lại không có ràng buộc bổ sung

Ví dụ:

Dữ liệu	Kết quả
`6 5` `1 2 4 7 7 13`	`5`

Giải thích: Một cách để chọn 5 bông hoa cho 2 bó hoa là:

Bó thứ nhất gồm 2 bông hoa lấy từ 2 cây hoa có “độ đẹp” 1, 4
Bó thứ hai gồm 3 bông hoa lấy từ 3 cây hoa có “độ đẹp” 2, 7, 7
Không có cách nào chọn 6 bông hoa hồng

Bài 5 (8 điểm)

Trường THCS nơi Dũng đang học có trồng một hàng cây xanh trông rất đẹp. Hàng cây gồm n cây xanh được đánh số thứ tự từ 1 đến n (theo hướng từ trái sang phải). Để đơn giản có thể coi hàng cây như trục toạ độ Ox và cây thứ i có toạ độ x_i (x₁ < x₂ < ⋯ < x_n).

Để tưới nước cho cây, nhà trường có kế hoạch lắp đặt m vòi tưới nước tự động. Vòi nước thứ i (i = 1, 2, …, m) được lắp tại vị trí cây t_i, có bán kính tưới nước là R_i. Điều này có ý nghĩa rằng vòi nước này tưới được cây t_i và tất cả các cây có khoảng cách đến t_i không vượt quá R_i.

Yêu cầu: Cho biết vị trí lắp đặt m vòi nước và bán kính tưới nước của m vòi này. Hãy đếm xem có bao nhiêu cây được tưới nước.

Dữ liệu: Nhập từ bàn phím

Dòng đầu tiên chứa hai số nguyên dương n, m (1 ≤ m ≤ n ≤ 10⁶)
Dòng thứ hai chứa n số nguyên x₁, x₂, …, x_n (0 < x₁ < x₂ < ⋯ < x_n ≤ 10⁹) lần lượt là toạ độ của các cây 1, 2, …, n.
Tiếp theo là m dòng, dòng thứ i chứa hai số nguyên dương t_i, R_i (1 ≤ t_i ≤ n; R_i ≤ 10⁹) lần lượt là số hiệu và bán kính tưới nước của vòi nước thứ i (i = 1, 2, …, m).

Hai số liên tiếp trên cùng một dòng cách nhau bằng khoảng trống (space)

Kết quả: Ghi ra màn hình một số nguyên duy nhất là số cây được tưới nước.

Ràng buộc:

Có 30% số tests ứng với 30% số điểm của bài có m = 1
30% số tests tiếp theo ứng với 30% số điểm của bài có n ≤ 2000
Các tests còn lại không có giới hạn bổ sung

Ví dụ:

Dữ liệu	Kết quả
`5 2` `1 3 5 7 9 11` `1 5` `4 2`	`5`

Giải thích: Vòi thứ nhất tưới được các cây số hiệu 1, 2, 3; vòi thứ hai tưới được các cây 3, 4, 5. Như vậy chỉ các cây 1, 2, 3, 4, 5 được tưới nước.

Với vòi tại cây t, dùng lower_bound và upper_bound trên dãy tọa độ tăng để tìm đoạn chỉ số các cây nằm trong [x[t] − R, x[t] + R]. Đánh dấu đoạn bằng mảng hiệu; cuối cùng đếm các vị trí có tổng dồn dương.

Lưu ý: ví dụ của đề ghi n = 5 nhưng dòng thứ hai có 6 tọa độ; chạy với n = 6 thì chương trình cho đúng kết quả 5.

Độ phức tạp: O((n + m) log n).

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, m;
    cin >> n >> m;
    vector<ll> x(n);
    for (ll &v : x)
        cin >> v;
    vector<int> diff(n + 1);
    while (m--) {
        int t;
        ll R;
        cin >> t >> R;
        --t;
        int l = lower_bound(x.begin(), x.end(), x[t] - R) - x.begin();
        int r = upper_bound(x.begin(), x.end(), x[t] + R) - x.begin();
        diff[l]++;
        diff[r]--;
    }
    int cur = 0, ans = 0;
    for (int i = 0; i < n; i++) {
        cur += diff[i];
        if (cur > 0)
            ans++;
    }
    cout << ans;
}

Th.S Trần Huy Phúc

Kỹ sư phần mềm @Adnovum & Bumbii Academy

Học Tiếng Anh với Bumbii English