HSG lớp 9 Hà Tĩnh 2025-2026

SỞ GIÁO DỤC VÀ ĐÀO TẠO HÀ TĨNH ĐỀ GÕ LẠI
(Đề thi có 03 trang, gồm 04 bài)

KỲ THI CHỌN HỌC SINH GIỎI TỈNH LỚP 9 Năm học 2025 - 2026
Môn thi: Tin học
Thời gian làm bài: 120 phút

Tổng quan đề thi

	Tiêu đề	Tên chương trình	Tệp dữ liệu	Tệp kết quả	Điểm
Bài 1	Đếm cặp số	`BAI1.*`	`BAI1.INP`	`BAI1.OUT`	4
Bài 2	Ước nguyên tố	`BAI2.*`	`BAI2.INP`	`BAI2.OUT`	6
Bài 3	Giá trị lớn nhất	`BAI3.*`	`BAI3.INP`	`BAI3.OUT`	6
Bài 4	Trung vị	`BAI4.*`	`BAI4.INP`	`BAI4.OUT`	4

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.

Bài 1. Đếm cặp số

Cho số nguyên dương k (1 ≤ k ≤ 10¹²).

Yêu cầu: Đếm số lượng các cặp số nguyên dương a, b thỏa mãn: a < b và a.b ≤ k.

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

Kết quả: Ghi ra tệp BAI1.OUT một số nguyên duy nhất là kết quả của bài toán.

Ràng buộc:

Có 80% số test ứng với 80% số điểm của bài thỏa mãn: k ≤ 10³.
20% số test còn lại ứng với 20% số điểm của bài không có ràng buộc gì thêm.

Ví dụ:

BAI1.INP	BAI1.OUT	Giải thích
`6`	`6`	Các cặp số thỏa mãn: (1,2), (1,3), (1,4), (1,5), (1,6), (2,3)

Bài 2. Ước nguyên tố

Số tự nhiên m được gọi là ước nguyên tố của số nguyên dương n nếu n chia hết cho m và m là số nguyên tố.

Ví dụ: Số 12 có 2 ước nguyên tố là 2 và 3; số 30 có 3 ước nguyên tố là 2, 3 và 5.

Yêu cầu: Cho Q truy vấn, mỗi truy vấn gồm ba số nguyên a, b, k. Với mỗi truy vấn, hãy xác định số lượng các số nguyên x thỏa mãn: a ≤ x ≤ b và có số lượng ước nguyên tố không nhỏ hơn k.

Dữ liệu: Vào từ tệp văn bản BAI2.INP có cấu trúc:

Dòng thứ nhất chứa số nguyên dương Q là số lượng truy vấn (1 ≤ Q ≤ 10⁵).
Q dòng tiếp theo, mỗi dòng chứa ba số nguyên a, b, k (1 ≤ a ≤ b ≤ 10⁶; 0 ≤ k ≤ 7).

Kết quả: Ghi ra tệp văn bản BAI2.OUT gồm Q dòng, mỗi dòng ghi một số nguyên duy nhất là kết quả tương ứng với mỗi truy vấn.

Ràng buộc:

Có 60% số test ứng với 60% số điểm của bài thỏa mãn: Q = 1; 1 ≤ a ≤ b ≤ 10³.
Có 20% số test khác ứng với 20% số điểm của bài thỏa mãn: Q = 1; 10³ < a ≤ b ≤ 10⁶.
20% số test còn lại ứng với 20% số điểm của bài không có ràng buộc gì thêm.

Ví dụ:

BAI2.INP	BAI2.OUT	Giải thích
`1` `25 30 2`	`3`	Từ 25 đến 30 có 3 số có từ 2 ước nguyên tố trở lên đó là 26, 28 và 30. Cụ thể: 26 có 2 ước nguyên tố là 2 và 13 28 có 2 ước nguyên tố là 2 và 7 30 có 3 ước nguyên tố là 2, 3 và 5

Bài 3. Giá trị lớn nhất

Cho dãy a gồm n số nguyên a₁, a₂, …, a_n và ba số nguyên x, y, z.

Yêu cầu: Tìm giá trị lớn nhất của biểu thức x.a_i + y.a_j + z.a_k (1 ≤ i < j < k ≤ n).

Dữ liệu: Vào từ tệp văn bản BAI3.INP có cấu trúc:

Dòng đầu tiên chứa số nguyên dương n (3 ≤ n ≤ 10⁶).
Dòng thứ hai chứa n số nguyên a₁, a₂, …, a_n (|a_i| ≤ 10⁵; 1 ≤ i ≤ n).
Dòng thứ ba chứa ba số nguyên x, y, z (|x|, |y|, |z| ≤ 10⁵).

Kết quả: Ghi ra tệp văn bản BAI3.OUT một số nguyên duy nhất là giá trị lớn nhất tìm được.

Ràng buộc:

Có 40% số test ứng với 40% số điểm của bài thỏa mãn: n ≤ 10².
Có 30% số test khác ứng với 30% số điểm của bài thỏa mãn: 10² < n ≤ 10⁶; x = y = z.
30% số test còn lại ứng với 30% số điểm của bài không có ràng buộc gì thêm.

Ví dụ:

BAI3.INP	BAI3.OUT	Giải thích
`5` `1 3 2 4 5` `3 8 2`	`51`	- Chọn ba số hạng a₂, a₄, a₅ - Giá trị của biểu thức là: x.a₂ + y.a₄ + z.a₅ = 3.3 + 8.4 + 2.5 = 51 (lớn nhất)

Bài 4. Trung vị

Cho mảng a gồm n số nguyên dương a₁, a₂, …, a_n và số nguyên dương M. Một đoạn con liên tiếp của mảng a là một dãy gồm các phần tử liên tiếp có dạng: a_i, a_i+1, …, a_j (1 ≤ i ≤ j ≤ n), độ dài là j − i + 1.

Trung vị của một đoạn con liên tiếp b có độ dài k được định nghĩa như sau:

Sắp xếp các phần tử của b theo thứ tự không giảm.
Khi đó:
- Nếu k lẻ: Trung vị là phần tử ở vị trí (k + 1)/2.
- Nếu k chẵn: Trung vị là phần tử ở vị trí k/2.

Yêu cầu: Hãy đếm số lượng đoạn con liên tiếp của mảng a có trung vị bằng M.

Dữ liệu: Vào từ tệp văn bản BAI4.INP có cấu trúc:

Dòng thứ nhất chứa hai số nguyên dương n, M (1 ≤ M < n ≤ 10⁶).
Dòng thứ hai chứa n số nguyên dương a₁, a₂, …, a_n (a_i ≤ 10⁶; 1 ≤ i ≤ n).

Kết quả: Ghi ra tệp văn bản BAI4.OUT một số nguyên duy nhất là kết quả của bài toán.

Ràng buộc:

Có 40% số test ứng với 40% số điểm của bài thỏa mãn: n ≤ 10².
Có 30% số test khác ứng với 30% số điểm của bài thỏa mãn: 10² < n ≤ 5.10³.
30% số test còn lại ứng với 30% số điểm của bài không có ràng buộc gì thêm.

Ví dụ:

BAI4.INP	BAI4.OUT	Giải thích
`5 2` `2 1 3 4 5`	`3`	Các đoạn con liên tiếp có trung vị bằng 2 là: `2` `2 1 3` `2 1 3 4`

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

Hướng dẫn giải và đáp án

Bài 1. Đếm cặp số

Xem hướng dẫn & lời giải

Hướng dẫn giải

Với mỗi a ≤ √k, mọi b thuộc [a + 1, ⌊k/a⌋] đều hợp lệ. Cộng trực tiếp số phần tử của từng khoảng.

Độ phức tạp: O(√k).

#include <bits/stdc++.h>
using namespace std;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    long long k;
    if (!(cin >> k))
        return 0;
    long long ans = 0;
    for (long long a = 1; a * a <= k; a++)
        ans += max(0LL, k / a - a);
    cout << ans;
}

Bài 2. Ước nguyên tố

Xem hướng dẫn & lời giải

Hướng dẫn giải

Sàng một lần để đếm số ước nguyên tố phân biệt của mọi số đến 10⁶, sau đó lập 8 mảng cộng dồn ứng với các giá trị k. Mỗi truy vấn trả lời trong O(1).

Độ phức tạp: O(V log log V + Q), với V = 10⁶.

#include <bits/stdc++.h>
using namespace std;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    const int V = 1000000;
    vector<unsigned char> w(V + 1);
    for (int p = 2; p <= V; p++)
        if (!w[p])
            for (int x = p; x <= V; x += p)
                w[x]++;
    vector<array<int, 8>> pre(V + 1);
    for (int i = 1; i <= V; i++) {
        pre[i] = pre[i - 1];
        for (int k = 0; k <= 7; k++)
            if (w[i] >= k)
                pre[i][k]++;
    }
    int Q;
    cin >> Q;
    while (Q--) {
        int a, b, k;
        cin >> a >> b >> k;
        cout << pre[b][k] - pre[a - 1][k] << '\n';
    }
}

Bài 3. Giá trị lớn nhất

Xem hướng dẫn & lời giải

Hướng dẫn giải

Duyệt từ trái sang phải, giữ ba giá trị tốt nhất sau khi đã chọn i, đã chọn i < j và đã chọn i < j < k. Cập nhật theo thứ tự ngược (k trước, i sau) để một phần tử không bị dùng hai lần.

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

#include <bits/stdc++.h>
using namespace std;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin >> n;
    vector<long long> a(n);
    for (auto &v : a)
        cin >> v;
    long long x, y, z;
    cin >> x >> y >> z;
    const long long N = LLONG_MIN / 4;
    long long d1 = N, d2 = N, d3 = N;
    for (long long v : a) {
        d3 = max(d3, d2 + z * v);
        d2 = max(d2, d1 + y * v);
        d1 = max(d1, x * v);
    }
    cout << d3;
}

Bài 4. Trung vị

Xem hướng dẫn & lời giải

Hướng dẫn giải

Gọi F(X) là số đoạn có trung vị (theo định nghĩa của đề) không nhỏ hơn X. Đổi phần tử ≥ X thành +1, còn lại thành −1; đoạn có trung vị ≥ X khi tổng dương, tức là cặp tổng tiền tố p_i < p_j với i < j. Đếm các cặp này bằng cây Fenwick.

Số đoạn có trung vị đúng bằng M là F(M) − F(M + 1).

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

#include <bits/stdc++.h>
using namespace std;
struct BIT {
    int n;
    vector<int> t;
    BIT(int n) : n(n), t(n + 1) {}
    void add(int x) {
        for (; x <= n; x += x & -x)
            t[x]++;
    }
    long long sum(int x) {
        long long s = 0;
        for (; x; x -= x & -x)
            s += t[x];
        return s;
    }
};
long long ge(const vector<int> &a, int x) {
    int n = a.size(), off = n + 2, cur = 0;
    BIT ft(2 * n + 5);
    long long ans = 0;
    ft.add(off);
    for (int v : a) {
        cur += (v >= x ? 1 : -1);
        ans += ft.sum(cur + off - 1);
        ft.add(cur + off);
    }
    return ans;
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, M;
    cin >> n >> M;
    vector<int> a(n);
    for (int &v : a)
        cin >> v;
    cout << ge(a, M) - ge(a, M + 1);
}

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