HSG lớp 9 Quảng Trị 2025-2026

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

KỲ THI CHỌN HỌC SINH GIỎI LỚP 9 Năm học 2025 - 2026 - Khóa ngày 09 tháng 3 năm 2026
Môn thi: Tin học
Thời gian: 150 phút (không kể thời gian giao đề)
Đề gồm có 02 trang và 04 câu

Tổng quan về bài thi

Tên bài	Tên tệp chương trình	Tên tệp INPUT	Tên tệp OUTPUT	Điểm
Đếm số	`CAU1.*`	`CAU1.INP`	`CAU1.OUT`	5,0
Đếm từ	`CAU2.*`	`CAU2.INP`	`CAU2.OUT`	5,0
Hộp quà	`CAU3.*`	`CAU3.INP`	`CAU3.OUT`	5,0
Giá trị dãy số	`CAU4.*`	`CAU4.INP`	`CAU4.OUT`	5,0

Dấu * là CPP, PY hoặc PAS;
Thời gian thực hiện 1 test/1s.

Câu 1. Đếm số

Số chính phương là bình phương của các số tự nhiên. Ví dụ: 4, 9, 16 là các số chính phương; 3, 8, 10 không phải là số chính phương.

Yêu cầu: Cho đoạn số nguyên [a, b], hãy đếm số lượng số chính phương có trong đoạn [a, b].

Dữ liệu vào từ tệp văn bản CAU1.INP có cấu trúc như sau:

Chứa hai số tự nhiên a, b cách nhau một dấu cách (1 ≤ a ≤ b ≤ 10⁹).

Kết quả ghi ra tệp văn bản CAU1.OUT số d là số lượng số chính phương có trong đoạn [a, b].

Subtask	Số điểm	Ràng buộc
1	4,0	1 ≤ a ≤ b ≤ 10⁶
2	1,0	10⁶ ≤ a ≤ b ≤ 10⁹

Ví dụ:

CAU1.INP	CAU1.OUT	Giải thích
`1 5`	`2`	1, 4 là các số chính phương
`10 20`	`1`	16 là số chính phương
`5 8`	`0`

Câu 2. Đếm từ

Từ là tập hợp các kí tự liên tiếp nhau có trong bảng mã ASCII được viết cách nhau bởi dấu cách. Ví dụ cho xâu kí tự “lop 9b THCS” có ba từ “lop”, “9b”, “THCS”.

Yêu cầu: Cho xâu S trong đó các kí tự được lấy từ tập {'0'..'9', 'A'..'Z', 'a'..'z'} và dấu cách, hãy đếm xem có bao nhiêu độ dài khác nhau của các từ ở trong xâu.

Dữ liệu vào từ trong tệp văn bản CAU2.INP có cấu trúc như sau:

Có một dòng duy nhất chứa xâu S (có ít nhất một từ).

Kết quả ghi ra tệp văn bản CAU2.OUT theo cấu trúc sau:

Dòng 1 ghi số dương d là số lượng độ dài khác nhau của các từ có trong xâu;
Dòng thứ i trong d dòng tiếp theo mỗi dòng ghi hai số x và y, trong đó x là độ dài của từ và y là số từ có độ dài tương ứng là x. Giá trị x trên mỗi dòng tăng dần theo độ dài của từ.

Subtask	Số điểm	Ràng buộc
1	3,0	Độ dài xâu kí tự không quá 10³
2	2,0	Độ dài xâu kí tự không quá 10⁶

Ví dụ:

CAU2.INP	CAU2.OUT	Giải thích
`Ky thi HSG THCS 2026`	`3` `2 1` `3 2` `4 2`	Có 3 độ dài khác nhau của các từ xuất hiện trong xâu: Các từ có độ dài 2: “Ky” Các từ có độ dài 3: “thi”, “HSG” Các từ có độ dài 4: “THCS”, “2026”

Câu 3. Hộp quà

Có n hộp quà, các hộp quà được đánh số từ 1 đến n, hộp thứ i có giá trị a_i (1 ≤ a_i ≤ m). Lớp Nam được cô giáo giao nhiệm vụ chuẩn bị K giỏ quà từ n hộp quà đã có, tuân thủ tất cả các quy tắc sau:

Mỗi giỏ quà gồm hai hộp quà;
Hộp quà thứ nhất được lấy từ các hộp quà có chỉ số từ 1 đến K, hộp quà thứ 2 được lấy từ các hộp quà có chỉ số từ K + 1 đến n;
Hộp quà thứ nhất có giá trị nhỏ hơn hộp quà thứ 2.

Ví dụ: Cho các hộp quà có giá trị lần lượt như sau: 2 1 4 2 3 2 4 5 2 3. Nam có thể ghép được 4 hộp quà có giá trị 2 1 4 2 với 6 hộp quà có giá trị 3 2 4 5 2 3 tạo thành 4 giỏ quà được ghép là {(2,3), (1,2), (4,5), (2,3)} hoặc {(2,3), (1,2), (4,5), (2,4)}.

Yêu cầu: Cho n hộp quà có giá trị a₁, a₂, …, a_n, hãy tìm K lớn nhất theo quy tắc trên.

Dữ liệu vào từ tệp văn bản CAU3.INP có cấu trúc như sau:

Dòng đầu tiên chứa hai số nguyên dương n, m (1 ≤ n ≤ 10⁵, 1 ≤ m ≤ 10⁹);
Dòng tiếp theo ghi n số nguyên dương a_i (1 ≤ a_i ≤ m);

Các số trong tệp cách nhau bởi dấu cách.

Kết quả ghi vào tệp văn bản CAU3.OUT là số K lớn nhất tìm được, nếu không có nghiệm thì in ra -1.

Subtask	Số điểm	Ràng buộc
1	2,0	1 ≤ n ≤ 100, 1 ≤ m ≤ 10³
2	1,5	100 ≤ n ≤ 5 * 10³, 1 ≤ m ≤ 10⁹
3	1,5	Không ràng buộc gì thêm

Ví dụ:

CAU3.INP	CAU3.OUT
`10 5` `2 1 4 2 3 2 4 5 2 3`	`4`
`5 6` `5 4 2 1 2`	`-1`
`3 3` `1 2 3`	`1`

Câu 4. Giá trị của dãy số

Cho dãy A gồm n số nguyên dương a₁, a₂, …, a_n. Một đoạn con liên tiếp của dãy A là đoạn a_l, a_(l+1), …, a_r với 1 ≤ l ≤ r ≤ n, giá trị đoạn con là độ chênh lệch của giá trị lớn nhất và giá trị nhỏ nhất của đoạn con. Giá trị của dãy số là tổng giá trị tất cả các đoạn con liên tiếp của dãy. Ví dụ: Cho dãy số 2 4 1 ta có các đoạn con liên tiếp {2}, {2, 4}, {2, 4, 1}, {4}, {4, 1}, {1}, giá trị dãy số là 0 + 3 + 0 + 3 + 0 + 2 = 8.

Yêu cầu: Với dãy số nguyên dương a₁, a₂, …, a_n có n phần tử, hãy tính giá trị của dãy số.

Dữ liệu vào từ tệp văn bản CAU4.INP có cấu trúc như sau:

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_n (|a_i| ≤ 10⁷);

Các số trong tệp cách nhau bởi dấu cách.

Kết quả ghi ra tệp văn bản CAU4.OUT một số nguyên duy nhất là giá trị của dãy số.

Subtask	Số điểm	Ràng buộc
1	1,5	1 ≤ n ≤ 100
2	1,5	1 ≤ n ≤ 3000
3	2,0	Không ràng buộc gì thêm

Ví dụ:

CAU4.INP	CAU4.OUT
`3` `2 4 1`	`8`

Thí sinh không được sử dụng tài liệu.

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

Câu 1. Đếm số

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

Hướng dẫn giải

Các số chính phương trong [a, b] ứng với các số nguyên x trong [⌈√a⌉, ⌊√b⌋]. Kết quả sqrt được hiệu chỉnh lại bằng phép nhân số nguyên để tránh sai số.

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

#include <bits/stdc++.h>
using namespace std;
using int64 = long long;
int main() {
    int64 a, b;
    cin >> a >> b;
    int64 lo = sqrt((long double)a), hi = sqrt((long double)b);
    while (lo * lo < a)
        lo++;
    while ((hi + 1) * (hi + 1) <= b)
        hi++;
    while (hi * hi > b)
        hi--;
    cout << max<int64>(0, hi - lo + 1);
}

Câu 2. Đếm từ

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

Hướng dẫn giải

Dùng stringstream tách từ theo mọi chuỗi khoảng trắng, đếm số từ theo độ dài bằng map; map tự sắp các độ dài tăng dần khi in.

Độ phức tạp: O(|S| + D log D).

#include <bits/stdc++.h>
using namespace std;
int main() {
    string s;
    getline(cin, s);
    map<int, int> cnt;
    stringstream ss(s);
    string w;
    while (ss >> w)
        cnt[w.size()]++;
    cout << cnt.size() << '\n';
    for (auto [l, c] : cnt)
        cout << l << ' ' << c << '\n';
}

Câu 3. Hộp quà

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

Hướng dẫn giải

Tìm kiếm nhị phân K trong [1, ⌊n/2⌋]. Với một K, sắp xếp K giá trị đầu và phần còn lại. Dùng hai con trỏ, ghép mỗi phần tử bên trái (từ nhỏ đến lớn) với phần tử bên phải nhỏ nhất lớn hơn nó; chọn phần tử phải nhỏ nhất để lại nhiều lựa chọn nhất cho các phần tử trái lớn hơn. Khi K tăng, bên trái nhiều phần tử hơn và bên phải ít đi nên tính khả thi không tăng.

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

#include <bits/stdc++.h>
using namespace std;
bool ok(const vector<long long> &a, int k) {
    if (2 * k > (int)a.size())
        return false;
    vector<long long> L(a.begin(), a.begin() + k), R(a.begin() + k, a.end());
    sort(L.begin(), L.end());
    sort(R.begin(), R.end());
    int j = 0;
    for (long long x : L) {
        while (j < (int)R.size() && R[j] <= x)
            j++;
        if (j == (int)R.size())
            return false;
        j++;
    }
    return true;
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    long long m;
    cin >> n >> m;
    vector<long long> a(n);
    for (auto &x : a)
        cin >> x;
    int lo = 1, hi = n / 2, ans = -1;
    while (lo <= hi) {
        int mid = (lo + hi) / 2;
        if (ok(a, mid))
            ans = mid, lo = mid + 1;
        else
            hi = mid - 1;
    }
    cout << ans;
}

Câu 4. Giá trị của dãy số

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

Hướng dẫn giải

Tổng cần tìm bằng tổng đóng góp khi mỗi a[i] là giá trị lớn nhất của đoạn trừ tổng đóng góp khi nó là giá trị nhỏ nhất. Dùng bốn ngăn xếp đơn điệu tìm biên gần nhất mỗi phía; một phía so sánh ngặt, phía kia không ngặt để đoạn có các phần tử bằng nhau chỉ được tính một lần.

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

#include <bits/stdc++.h>
using namespace std;
using int64 = long long;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin >> n;
    vector<int64> a(n);
    for (auto &x : a)
        cin >> x;
    vector<int> pl(n), nl(n), pg(n), ng(n), st;
    for (int i = 0; i < n; i++) {
        while (!st.empty() && a[st.back()] >= a[i])
            st.pop_back();
        pl[i] = st.empty() ? -1 : st.back();
        st.push_back(i);
    }
    st.clear();
    for (int i = n - 1; i >= 0; i--) {
        while (!st.empty() && a[st.back()] > a[i])
            st.pop_back();
        nl[i] = st.empty() ? n : st.back();
        st.push_back(i);
    }
    st.clear();
    for (int i = 0; i < n; i++) {
        while (!st.empty() && a[st.back()] <= a[i])
            st.pop_back();
        pg[i] = st.empty() ? -1 : st.back();
        st.push_back(i);
    }
    st.clear();
    for (int i = n - 1; i >= 0; i--) {
        while (!st.empty() && a[st.back()] < a[i])
            st.pop_back();
        ng[i] = st.empty() ? n : st.back();
        st.push_back(i);
    }
    __int128 ans = 0;
    for (int i = 0; i < n; i++)
        ans +=
            (__int128)a[i] * (i - pg[i]) * (ng[i] - i) - (__int128)a[i] * (i - pl[i]) * (nl[i] - i);
    long long out = (long long)ans;
    cout << out;
}

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