HSG lớp 9 Đà Nẵng 2025-2026

SỞ GIÁO DỤC VÀ ĐÀO TẠO THÀNH PHỐ ĐÀ NẴNG ĐỀ CHÍNH THỨC
(Đề thi gồm có 02 trang)

KỲ THI CHỌN HỌC SINH GIỎI CẤP THÀNH PHỐ Năm học 2025 - 2026
Môn thi: Tin học 9 - Ngày thi: 24/3/2026
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	File dữ liệu vào	File dữ liệu ra
Bài 1	ROBOT	`ROBOT.*`	`ROBOT.INP`	`ROBOT.OUT`
Bài 2	NGUYÊN TỐ LỆCH	`NTLECH.*`	`NTLECH.INP`	`NTLECH.OUT`
Bài 3	VẬN CHUYỂN	`VANCHUYEN.*`	`VANCHUYEN.INP`	`VANCHUYEN.OUT`
Bài 4	ĐẸP HOÀN HẢO	`DHH.*`	`DHH.INP`	`DHH.OUT`

Chú ý: Dấu * có thể là pas; c; cpp hoặc py tương ứng với ngôn ngữ lập trình là Free Pascal; C/C++ hoặc Python.

Bài 1. ROBOT (2,0 điểm)

Cho một xâu S có độ dài N kí tự, ghi lại hành trình di chuyển của một Robot trên lưới các ô vuông. Trong xâu S chứa các kí tự U, D, L, R tương ứng với các hướng di chuyển, mỗi lần di chuyển một ô vuông với: U - lên trên, D - xuống dưới, L - sang trái, R - sang phải.

Yêu cầu: Hãy tìm tọa độ của Robot khi kết thúc hành trình, biết rằng ban đầu Robot xuất phát tại tọa độ (0, 0).

Dữ liệu vào: Đọc từ tệp ROBOT.INP gồm:

Dòng thứ nhất chứa số nguyên dương N (N ≤ 10⁵).
Dòng thứ hai chứa xâu S.

Dữ liệu ra: Ghi ra tệp ROBOT.OUT gồm hai số nguyên dương x và y cách nhau một kí tự trống, là tọa độ của Robot khi kết thúc hành trình.

Ví dụ:

ROBOT.INP	ROBOT.OUT
`10` `UULLDRDDR`	`0 -1`

Bài 2. NGUYÊN TỐ LỆCH (3,0 điểm)

Số nguyên tố lệch là một số nguyên dương thỏa mãn cả 2 điều kiện: là số nguyên tố và số lượng chữ số chẵn khác số lượng chữ số lẻ.

Yêu cầu: Cho dãy có N số nguyên dương A₁, A₂, …, A_N. Hãy đếm số lượng số nguyên tố lệch trong dãy.

Dữ liệu vào: Đọc từ tệp NTLECH.INP gồm:

Dòng thứ nhất chứa số nguyên dương N (N ≤ 10⁵).
Dòng thứ hai chứa N số nguyên dương A₁, A₂, …, A_N (A_i ≤ 10⁶) mỗi số cách nhau một ký tự trống.

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

Ví dụ:

NTLECH.INP	NTLECH.OUT	Giải thích
`5` `23 232 311 15 60`	`1`	Các số nguyên tố trong dãy số là 23, 311. Trong đó 23 không phải số nguyên tố lệch vì có một chữ số chẵn và một chữ số lẻ, số 311 là số nguyên tố lệch vì có ba chữ số lẻ và không chữ số chẵn.

Ràng buộc:

Subtask 1: 40% số điểm có 1 ≤ N ≤ 10²; A_i ≤ 10³;
Subtask 2: 40% số điểm có 10² < N ≤ 10³; 10³ < A_i ≤ 10⁴;
Subtask 3: 20% số điểm có 10³ < N ≤ 10⁵; 10⁴ < A_i ≤ 10⁶.

Bài 3. VẬN CHUYỂN (3,0 điểm)

Một công ty Logistics có K Drone giao hàng. Công ty nhận một đơn hàng vận chuyển N thùng hàng, các thùng hàng được đánh số thứ tự từ 1 đến N, thùng hàng thứ i có trọng lượng là A_i.

Mỗi Drone tham gia sẽ vận chuyển các thùng hàng liên tiếp trong đơn hàng mà không làm thay đổi thứ tự các thùng hàng. Năng lượng vận hành của mỗi Drone được tính bằng tổng trọng lượng của các thùng hàng trên Drone. Chi phí của đơn hàng được tính bằng năng lượng vận hành lớn nhất trong các Drone tham gia vận chuyển.

Yêu cầu: Tính chi phí thấp nhất để vận chuyển đơn hàng.

Dữ liệu vào: Đọc từ tệp VANCHUYEN.INP gồm:

Dòng thứ nhất chứa số nguyên dương N và K mỗi số cách nhau một kí tự trống (N ≥ K).
Dòng thứ hai chứa N số nguyên dương A₁, A₂, …, A_N mỗi số cách nhau một ký tự trống.

Dữ liệu ra: Ghi ra tệp VANCHUYEN.OUT một số nguyên duy nhất là chi phí thấp nhất để vận chuyển đơn hàng.

Ví dụ:

VANCHUYEN.INP	VANCHUYEN.OUT	Giải thích
`5 2` `1 3 2 3 5`	`8`	Drone 1 vận chuyển các thùng hàng có trọng lượng 1, 3, 2. Drone 2 vận chuyển các thùng hàng có trọng lượng 3, 5. Chi phí vận chuyển đơn hàng được tính bằng năng lượng vận hành của Drone 2 = 3 + 5 = 8.
`5 3` `1 1 2 3 4`	`4`	Drone 1 vận chuyển các thùng hàng có trọng lượng 1, 1, 2. Drone 2 vận chuyển các thùng hàng có trọng lượng 3. Drone 3 vận chuyển các thùng hàng có trọng lượng 4. Chi phí vận chuyển đơn hàng được tính bằng năng lượng vận hành của Drone 1 = 1 + 1 + 2 = 4 hoặc Drone 3 = 4.

Ràng buộc:

Subtask 1: 20% số điểm có 2 ≤ N ≤ 10; 1 ≤ A_i ≤ 100; K = 2;
Subtask 2: 30% số điểm có 10 ≤ N ≤ 100; 1 ≤ A_i ≤ 1000; 3 ≤ K ≤ 10;
Subtask 3: 50% số điểm có 100 ≤ N ≤ 10⁵; 1 ≤ A_i ≤ 10⁹; 3 ≤ K ≤ 10³.

Bài 4. ĐẸP HOÀN HẢO (2,0 điểm)

Đoạn con của dãy số là một dãy các số được tạo thành từ các phần tử liên tiếp của dãy số ban đầu.

Độ đẹp của một dãy số là một số nguyên dương X nhỏ nhất, sao cho ta có thể chia dãy số ban đầu thành X đoạn con không giao nhau và tổng của tất cả các số trong mỗi đoạn con không lớn hơn S. Ví dụ: Với S = 8, đoạn [2, 3, 5] có thể chia thành hai hoặc ba đoạn có tổng mỗi đoạn con không lớn hơn S: ([2, 3], [5]) hoặc ([2], [3, 5]) hoặc ([2], [3], [5]). Vì cần tìm X nhỏ nhất nên đoạn [2, 5, 3] có độ đẹp là 2.

Độ đẹp hoàn hảo của dãy số là tổng độ đẹp tất cả các đoạn con của nó.

Yêu cầu: Cho dãy số nguyên dương A₁, A₂, …, A_N. Tính độ đẹp hoàn hảo của dãy số đã cho.

Dữ liệu vào: Đọc từ tệp DHH.INP gồm:

Dòng thứ nhất chứa hai số nguyên dương N và S cách nhau một ký tự trống (N ≤ 10⁵, S ≤ 10⁹).
Dòng thứ hai chứa N số nguyên dương A₁, A₂, …, A_N (A_i ≤ 10⁶) mỗi số cách nhau một ký tự trống.

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

Ví dụ:

DHH.INP	DHH.OUT	Giải thích
`4 8` `1 2 5 3`	`12`	Dãy 1, 2, 5, 3 có các đoạn con là: [1], [2], [5], [3], [1,2], [2,5], [5,3], [1,2,5], [2,5,3], [1,2,5,3]. Trong đó: [1] có độ đẹp là 1, [2] có độ đẹp là 1, [5] có độ đẹp là 1, [3] có độ đẹp là 1, [1,2] có độ đẹp là 1, [2,5] có độ đẹp là 1, [5,3] có độ đẹp là 1, [1,2,5] có độ đẹp là 1, [2,5,3] có độ đẹp là 2, [1,2,5,3] có độ đẹp là 2; Vậy độ đẹp hoàn hảo bằng: 1+1+1+1+1+1+1+1+2+2 = 12.

Ràng buộc:

Subtask 1: 20% số điểm có N ≤ 10; 1 ≤ A_i ≤ 10⁵; 10⁶ ≤ S ≤ 10⁹;
Subtask 2: 20% số điểm có N ≤ 10²; A_i ≤ 10³; 10 ≤ S ≤ 10⁹;
Subtask 3: 30% số điểm có N ≤ 10³; A_i ≤ 10⁴; 10 ≤ S ≤ 10⁹;
Subtask 4: 30% số điểm còn lạ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. ROBOT (2,0 điểm)

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

Hướng dẫn giải

Mô phỏng hành trình: cộng hoặc trừ tọa độ theo từng ký tự U, D, L, R.

Lưu ý: ví dụ của đề ghi N = 10 nhưng xâu chỉ có 9 ký tự; chương trình đọc cả xâu nên không bị ảnh hưởng.

Độ 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, x = 0, y = 0;
    string s;
    cin >> n >> s;
    for (char c : s) {
        if (c == 'U')
            y++;
        else if (c == 'D')
            y--;
        else if (c == 'L')
            x--;
        else
            x++;
    }
    cout << x << ' ' << y;
}

Bài 2. NGUYÊN TỐ LỆCH (3,0 điểm)

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

Hướng dẫn giải

Sàng Eratosthenes đến 10⁶. Với mỗi số nguyên tố trong dãy, đếm số chữ số chẵn và lẻ; hai số lượng khác nhau thì tăng đáp án.

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

#include <bits/stdc++.h>
using namespace std;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    const int M = 1000000;
    vector<bool> p(M + 1, true);
    p[0] = p[1] = false;
    for (int i = 2; i * i <= M; i++)
        if (p[i])
            for (int j = i * i; j <= M; j += i)
                p[j] = false;
    int n, ans = 0;
    cin >> n;
    while (n--) {
        int x, t, e = 0, o = 0;
        cin >> x;
        t = x;
        while (t) {
            ((t % 10) % 2 ? o : e)++;
            t /= 10;
        }
        if (p[x] && e != o)
            ans++;
    }
    cout << ans;
}

Bài 3. VẬN CHUYỂN (3,0 điểm)

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

Hướng dẫn giải

Tìm kiếm nhị phân chi phí C trong đoạn [max(A), tổng A]. Với một C, tham lam xếp nhiều thùng liên tiếp nhất có thể lên mỗi Drone; số Drone thu được là ít nhất. C khả thi khi số Drone không vượt K.

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

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, k;
    cin >> n >> k;
    vector<ll> a(n);
    ll lo = 0, hi = 1;
    for (ll &x : a) {
        cin >> x;
        lo = max(lo, x);
        hi += x;
    }
    auto ok = [&](ll c) {
        int seg = 1;
        ll s = 0;
        for (ll x : a) {
            if (s + x > c)
                seg++, s = x;
            else
                s += x;
        }
        return seg <= k;
    };
    lo--;
    while (lo + 1 < hi) {
        ll m = (lo + hi) / 2;
        if (ok(m))
            hi = m;
        else
            lo = m;
    }
    cout << hi;
}

Bài 4. ĐẸP HOÀN HẢO (2,0 điểm)

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

Hướng dẫn giải

Gọi nxt[i] là vị trí ngay sau đoạn dài nhất bắt đầu tại i có tổng không quá S. Với mọi điểm cuối trước nxt[i], độ đẹp bằng 1; từ nxt[i] trở đi, độ đẹp bằng 1 cộng độ đẹp của đoạn bắt đầu tại nxt[i]. Do đó dp[i] = n − i + 1 + dp[nxt[i]].

Tính nxt bằng cửa sổ trượt, tính dp từ phải sang trái; đáp án là tổng các dp[i].

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

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    ll S;
    cin >> n >> S;
    vector<ll> a(n + 1);
    for (int i = 1; i <= n; i++)
        cin >> a[i];
    vector<int> nxt(n + 2, n + 1);
    ll sum = 0;
    int r = 0;
    for (int l = 1; l <= n; l++) {
        while (r < n && sum + a[r + 1] <= S)
            sum += a[++r];
        nxt[l] = r + 1;
        if (r >= l)
            sum -= a[l];
        else
            r = l;
    }
    vector<ll> dp(n + 2);
    ll ans = 0;
    for (int i = n; i >= 1; i--) {
        dp[i] = n - i + 1 + (nxt[i] <= n ? dp[nxt[i]] : 0);
        ans += dp[i];
    }
    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