HSG THCS Tuyên Quang 2025-2026

SỞ GIÁO DỤC VÀ ĐÀO TẠO TUYÊN QUANG ĐỀ CHÍNH THỨC

ĐỀ THI CHỌN HỌC SINH GIỎI CẤP TỈNH LỚP 9 THCS Năm học: 2025 - 2026
Môn thi: Tin học
Thời gian: 150 phút (không kể thời gian giao đề)

Tổng quan đề thi

Tên bài	File chương trình	Dữ liệu vào	Dữ liệu ra	Điểm
Bài 1	`TROCHOI.*`	Bàn phím	Màn hình	5,0
Bài 2	`BOISO.*`	Bàn phím	Màn hình	5,0
Bài 3	`BINHCHON.*`	Bàn phím	Màn hình	5,0
Bài 4	`CHUPANH.*`	Bàn phím	Màn hình	5,0

Dấu * được thay thế bởi một trong ba phần mở rộng là: PAS, CPP hoặc PY của ngôn ngữ lập trình sử dụng tương ứng là Pascal, C++ hoặc Python.

Thí sinh bắt buộc phải đặt tên file chương trình như trên và lưu vào thư mục có tên SBD của mình, thí dụ: D:\04001.

Bài 1 (5,0 điểm). TRÒ CHƠI

Để chào mừng Xuân 2026, Trường THCS X tổ chức một buổi ngoại khoá chủ đề “Ngày xuân Hạnh phúc”. Trong buổi ngoại khoá, học sinh sẽ được tham gia các hoạt động: viết câu đối, gói bánh chưng, bày mâm ngũ quả và chơi các trò chơi. Trò chơi Đua thuyền trên cạn được rất nhiều học sinh hưởng ứng. Theo thể lệ, học sinh các lớp sẽ tham gia chơi với 2 nội dung:

Nội dung 1: mỗi đội có 5 học sinh.
Nội dung 2: mỗi đội có 3 học sinh.

Trường có T lớp. Mỗi lớp có n học sinh tham gia chơi.

Yêu cầu: Với từng lớp, hãy xác định số đội chơi ít nhất cần lập để đảm bảo có đúng n học sinh được tham gia.

Dữ liệu vào:

Dòng 1: số nguyên dương T là số lượng lớp (1 ≤ T ≤ 10⁵);
T dòng tiếp theo, mỗi dòng chứa một số nguyên n (1 ≤ n ≤ 5000).

Kết quả: Gồm T dòng, dòng thứ i in ra số đội chơi ít nhất cần lập để đảm bảo đúng n học sinh tham gia; in ra -1 nếu không thể lập đội chơi đúng yêu cầu.

Ví dụ:

INPUT	OUTPUT	Giải thích
`4` `1` `8` `11` `14`	`-1` `2` `3` `4`	1 học sinh: Không thể lập đội chơi. 8 học sinh: 5 + 3 → lập được 2 đội chơi. 11 học sinh: 5 + 3 + 3 → lập được 3 đội chơi. 14 học sinh: 5 + 3 + 3 + 3 → lập được 4 đội chơi.

Bài 2 (5,0 điểm). BỘI SỐ ĐẶC BIỆT

Bo đang luyện thi vào lớp 10 chuyên Tin của trường THPT chuyên A. Chủ đề thầy giáo giao cho Bo tuần này là số học, trong quá trình học tập Bo phát hiện ra một điều thú vị về bội của một số và đặt tên là Bội số đặc biệt. Với một số nguyên dương P không chia hết cho 2 và 5. Số X được gọi là một bội số đặc biệt của P nếu X chia hết cho P và X chỉ chứa toàn chữ số 9.

Ví dụ: Với P = 7 thì X = 999999 là một bội số đặc biệt của số P.

Cho trước hai số nguyên dương P và M.

Yêu cầu: Cho biết có bao nhiêu số X là bội số đặc biệt của P và X có số chữ số không vượt quá M.

Dữ liệu vào: Gồm hai số nguyên P và M trên cùng một dòng.

Kết quả: In ra một số duy nhất là số lượng các số X thoả mãn yêu cầu.

Ví dụ:

INPUT	OUTPUT	Giải thích
`7 7`	`1`	Với P = 7 và M = 7: có duy nhất một số X = 999999 thoả mãn.

Ràng buộc:

Subtask 1 (60% số điểm): P < 10⁴; M ≤ 18.
Subtask 2 (40% số điểm): 10⁴ ≤ P < 10⁶; M ≤ 10⁷.

Bài 3 (5,0 điểm). BÌNH CHỌN

Nhân dịp chào mừng ngày nhà giáo Việt Nam 20/11, Trường THCS X tổ chức cuộc thi làm video với chủ đề “Thầy cô trong mắt em”. Các tác phẩm dự thi sẽ được đăng tải trên fanpage của nhà trường để bình chọn bằng các lượt thích và chia sẻ. Mỗi lượt thích được tính 1 điểm, mỗi lượt chia sẻ được tính 2 điểm.

Kết thúc cuộc thi, ban tổ chức xuất được danh sách gồm n số nguyên dương a₁, a₂, …, a_n, trong đó a_i là số điểm bình chọn của tác phẩm thứ i.

Ban tổ chức cần xử lí q truy vấn.

Yêu cầu: Với mỗi truy vấn, hãy cho biết có bao nhiêu tác phẩm có đúng k điểm bình chọn.

Dữ liệu vào:

Dòng 1: Hai số nguyên dương n và q;
Dòng 2: n số nguyên dương a₁, a₂, …, a_n;
q dòng tiếp theo, mỗi dòng một số nguyên k.

Kết quả: In ra q dòng, dòng thứ i là số lượng tác phẩm có đúng k_i điểm bình chọn.

Ví dụ:

INPUT	OUTPUT	Giải thích
`7 3` `4 2 7 2 5 2 1` `2` `8` `1`	`3` `0` `1`	Có 3 tác phẩm có điểm bình chọn là 2. Không có tác phẩm nào có điểm bình chọn là 8. Có 1 tác phẩm có điểm bình chọn là 1.

Ràng buộc:

Subtask 1 (30% số điểm): 1 ≤ n, q < 2.10³.
Subtask 2 (30% số điểm): 2.10³ ≤ n ≤ 10⁵; 1 ≤ q ≤ 10⁵; a_i, k ≤ 10⁶.
Subtask 3 (40% số điểm): 2.10³ ≤ n ≤ 10⁵; 1 ≤ q ≤ 10⁵; a_i, k ≤ 10⁹.

Bài 4 (5,0 điểm). CHỤP ẢNH

Dọc theo con đường dẫn vào nhà ông bà BiBo được trang trí bởi n chậu hoa, mỗi chậu hoa trồng một loại hoa khác nhau. Chậu hoa thứ i có a_i bông hoa. BiBo quyết định chọn một dãy các chậu hoa liên tiếp dọc theo lối đi để bố trí khu vực chụp ảnh cho khách đến chơi nhà. Để khu vực chụp ảnh không quá đơn điệu, BiBo muốn dãy các chậu hoa được chọn có đúng k chậu hoa có số bông hoa là số lẻ. Vì có quá nhiều cách chọn, BiBo đang phân vân không biết chọn như thế nào.

Yêu cầu: Em hãy giúp BiBo đếm số cách chọn dãy các chậu hoa thoả mãn điều kiện đưa ra.

Dữ liệu vào:

Dòng 1: Hai số nguyên n, k (0 ≤ k ≤ n);
Dòng 2: n số nguyên a₁, a₂, …, a_n.

Kết quả: In ra một số nguyên duy nhất thỏa mãn yêu cầu bài toán.

Ví dụ:

INPUT	OUTPUT	Giải thích
`4 2` `1 3 2 3`	`3`	Có 3 cách chọn thoả mãn ở các vị trí bắt đầu và kết thúc là (1, 2), (1, 3) và (2, 4).

Ràng buộc:

Subtask 1 (30% số điểm): 1 ≤ n < 100;
Subtask 2 (30% số điểm): 100 ≤ n ≤ 5.10³.
Subtask 3 (40% số điểm): không có ràng buộc gì thêm.

--- HẾT ---

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

Bài 1 (5,0 điểm). TRÒ CHƠI

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

Hướng dẫn giải

Cần biểu diễn n = 5x + 3y với x + y nhỏ nhất. Vì n ≤ 5000, thử mọi x từ 0 đến n/5 và kiểm tra phần còn lại n − 5x có chia hết cho 3 không. Không có phương án nào thì in −1.

Độ phức tạp: O(n) mỗi lớp.

#include <bits/stdc++.h>
using namespace std;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int T;
    cin >> T;
    while (T--) {
        int n;
        cin >> n;
        int ans = INT_MAX;
        for (int x = 0; 5 * x <= n; ++x)
            if ((n - 5 * x) % 3 == 0)
                ans = min(ans, x + (n - 5 * x) / 3);
        cout << (ans == INT_MAX ? -1 : ans) << '\n';
    }
}

Bài 2 (5,0 điểm). BỘI SỐ ĐẶC BIỆT

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

Hướng dẫn giải

Gọi r(len) là số dư khi chia số gồm len chữ số 9 cho P. Ta có r(0) = 0 và r(len) = (10 · r(len − 1) + 9) mod P. Duyệt len từ 1 đến M, mỗi lần số dư bằng 0 thì có thêm một số thỏa mãn. Không bao giờ phải lưu số có tới 10⁷ chữ số.

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

#include <bits/stdc++.h>
using namespace std;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int p, m;
    cin >> p >> m;
    int r = 0, ans = 0;
    for (int len = 1; len <= m; ++len) {
        r = ((long long)r * 10 + 9) % p;
        if (r == 0)
            ++ans;
    }
    cout << ans;
}

Bài 3 (5,0 điểm). BÌNH CHỌN

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

Hướng dẫn giải

Đếm tần suất từng mức điểm bằng bảng băm. Mỗi truy vấn trả về ngay tần suất của k.

Độ phức tạp: O(n + q) kỳ vọng.

#include <bits/stdc++.h>
using namespace std;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, q;
    cin >> n >> q;
    unordered_map<long long, int> f;
    f.reserve(n * 2);
    while (n--) {
        long long x;
        cin >> x;
        ++f[x];
    }
    while (q--) {
        long long k;
        cin >> k;
        cout << f[k] << '\n';
    }
}

Bài 4 (5,0 điểm). CHỤP ẢNH

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

Hướng dẫn giải

Đổi mỗi a_i thành 1 nếu lẻ, 0 nếu chẵn. Một đoạn có đúng k số lẻ khi hiệu hai tổng tiền tố bằng k. Khi đang ở tổng tiền tố s, số đoạn kết thúc tại đây bằng số lần tổng s − k đã xuất hiện trước đó.

Độ 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, k;
    cin >> n >> k;
    vector<long long> cnt(n + 1);
    cnt[0] = 1;
    int pref = 0;
    long long ans = 0;
    for (int i = 0, x; i < n; ++i) {
        cin >> x;
        pref += abs(x) % 2;
        if (pref >= k)
            ans += cnt[pref - k];
        ++cnt[pref];
    }
    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