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_n. Một dãy con liên tiếp là dãy có dạng a_i, a_i+1, …, a_j (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_n (1 ≤ a_i ≤ 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_i ≤ 2 với mọi i = 1, 2, …, n và a_i ≤ a_i+1 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_n 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_i bất kì của dãy và thay thế số a_i bằng số ⌊a_i/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_i bất kì của dãy và thay thế a_i bằng giá trị lớn nhất của hai số a_i − 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_i 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_i. 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_i (1 ≤ a_i ≤ 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_n;
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_n, dãy thứ hai gồm các số b₁, b₂, …, b_n.

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_i, a_i+1, …, a_j bằng số nhỏ nhất của các số b_i, b_i+1, …, b_j.

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_n (1 ≤ |a_i| ≤ 10⁹);
Dòng thứ ba chứa n số nguyên b₁, b₂, …, b_n (1 ≤ |b_i| ≤ 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_n, b₁ ≤ b₂ ≤ ⋯ ≤ b_n;
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.

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

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

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

Hướng dẫn giải

Mã hóa thứ Hai đến Chủ nhật thành 0..6. Duyệt d ngày: ngày có chỉ số dưới 5 nhận a, hai ngày cuối tuần nhận b.

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

#include <bits/stdc++.h>
using namespace std;
int main() {
    long long k, d, a, b;
    cin >> k >> d >> a >> b;
    long long ans = 0;
    for (int i = 0; i < d; ++i) {
        int day = (k - 2 + i) % 7;
        ans += (day < 5 ? a : b);
    }
    cout << ans;
}

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

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

Hướng dẫn giải

Dùng cửa sổ trượt với bảng đếm các giá trị. Mở rộng đầu phải; khi có quá k giá trị khác nhau thì thu đầu trái. Mỗi khi có đúng k giá trị, cập nhật độ dài lớn nhất.

Độ 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<int> a(n), f(4);
    for (int &x : a)
        cin >> x;
    int l = 0, distinct = 0, ans = 0;
    for (int r = 0; r < n; ++r) {
        if (f[a[r]]++ == 0)
            ++distinct;
        while (distinct > k)
            if (--f[a[l++]] == 0)
                --distinct;
        if (distinct == k)
            ans = max(ans, r - l + 1);
    }
    cout << ans;
}

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

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

Hướng dẫn giải

Quy hoạch động theo số phép loại 1 và loại 2 đã dùng: dp[x][y] là tổng nhỏ nhất của phần đã xét. Mỗi phần tử có bốn lựa chọn: không làm gì, chia đôi, trừ b, hoặc dùng cả hai (lấy kết quả nhỏ hơn giữa hai thứ tự). Chỉ cần lớp trước nên bộ nhớ O(k1 · k2).

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

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll INF = (1LL << 62);
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, K1, K2;
    ll b;
    cin >> n >> b >> K1 >> K2;
    vector<ll> dp((K1 + 1) * (K2 + 1), INF), ndp;
    auto id = [&](int x, int y) { return x * (K2 + 1) + y; };
    dp[0] = 0;
    for (int z = 0; z < n; ++z) {
        ll a;
        cin >> a;
        ndp.assign(dp.size(), INF);
        for (int x = 0; x <= K1; ++x)
            for (int y = 0; y <= K2; ++y)
                if (dp[id(x, y)] < INF) {
                    ll v = dp[id(x, y)];
                    ndp[id(x, y)] = min(ndp[id(x, y)], v + a);
                    if (x < K1)
                        ndp[id(x + 1, y)] = min(ndp[id(x + 1, y)], v + a / 2);
                    if (y < K2)
                        ndp[id(x, y + 1)] = min(ndp[id(x, y + 1)], v + max(0LL, a - b));
                    if (x < K1 && y < K2) {
                        ll both = min(max(0LL, a / 2 - b), max(0LL, a - b) / 2);
                        ndp[id(x + 1, y + 1)] = min(ndp[id(x + 1, y + 1)], v + both);
                    }
                }
        dp.swap(ndp);
    }
    cout << *min_element(dp.begin(), dp.end());
}

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

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

Hướng dẫn giải

Với đầu trái l cố định, hàm F(r) = max(a[l..r]) − min(b[l..r]) không giảm theo r. Các đoạn cần đếm là các r có F(r) = 0. Dùng bảng thưa (sparse table) để truy vấn max/min trong O(1), rồi tìm kiếm nhị phân hai lần: vị trí đầu tiên F ≥ 0 và vị trí đầu tiên F > 0; hiệu hai vị trí là số đoạn hợp lệ với đầu trái l.

Độ phức tạp: O(n 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;
    cin >> n;
    int K = 1;
    while ((1 << K) <= n)
        ++K;
    vector<vector<ll>> mx(K, vector<ll>(n)), mn(K, vector<ll>(n));
    for (ll &x : mx[0])
        cin >> x;
    for (ll &x : mn[0])
        cin >> x;
    for (int k = 1; k < K; ++k)
        for (int i = 0; i + (1 << k) <= n; ++i) {
            mx[k][i] = max(mx[k - 1][i], mx[k - 1][i + (1 << (k - 1))]);
            mn[k][i] = min(mn[k - 1][i], mn[k - 1][i + (1 << (k - 1))]);
        }
    vector<int> lg(n + 1);
    for (int i = 2; i <= n; ++i)
        lg[i] = lg[i / 2] + 1;
    auto diff = [&](int l, int r) {
        int k = lg[r - l + 1];
        return max(mx[k][l], mx[k][r - (1 << k) + 1]) - min(mn[k][l], mn[k][r - (1 << k) + 1]);
    };
    long long ans = 0;
    for (int l = 0; l < n; ++l) {
        int lo = l - 1, hi = n;
        while (lo + 1 < hi) {
            int m = (lo + hi) / 2;
            if (diff(l, m) >= 0)
                hi = m;
            else
                lo = m;
        }
        int first = hi;
        lo = l - 1;
        hi = n;
        while (lo + 1 < hi) {
            int m = (lo + hi) / 2;
            if (diff(l, m) > 0)
                hi = m;
            else
                lo = m;
        }
        ans += hi - first;
    }
    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