HSG THCS An Giang 2025-2026

TỈNH AN GIANG ĐỀ THI CHÍNH THỨC

KỲ THI CHỌN HỌC SINH GIỎI CẤP TỈNH Năm học 2025 - 2026
Môn: Tin học - Ngày thi: 06/03/2026
Thời gian: 150 phút (không kể thời gian giao đề)
(Đề thi có 03 trang, gồm 04 bài)

Tổng quan bài thi

Bài	Tên bài	File chương trình	Điểm
1	Ngôi nhà	`ngoinha.*`	3,0
2	Vị trí	`vitri.*`	6,0
3	Chuẩn hoá	`chuanhoa.*`	6,0
4	Độ dài đoạn	`doandai.*`	5,0

Chú ý:

Dấu * được thay thế bởi pas, py, c/cpp, sb3 của ngôn ngữ lập trình được sử dụng tương ứng là Pascal, Python, C/C++, Scratch.
Đối với Python chỉ sử dụng thư viện chuẩn không import/add gì thêm.
Đối với C++ chỉ dùng thư viện iostream, cstring, cmath, algorithm.

Bài 1. Ngôi nhà (3,0 điểm)

Có N ngôi nhà xếp thành hàng ngang (1 ≤ N ≤ 500). Chiều cao các ngôi nhà là H[1], H[2], …, H[N]. Qui ước bãi biển ở bên phải dãy ngôi nhà theo hướng từ trước nhìn vào nhà. Một ngôi nhà nhìn thấy bãi biển nếu tất cả các ngôi nhà bên phải nó đều thấp hơn nó.

Yêu cầu: Viết chương trình tính số lượng ngôi nhà nhìn thấy bãi biển.

Dữ liệu vào: Cho trong tập tin BAI01.INP gồm nhiều dòng:

Dòng thứ nhất chứa số tự nhiên N (1 ≤ N ≤ 500);
Dòng thứ hai gồm N số tự nhiên biểu thị độ cao các ngôi nhà (H[i] ≤ 100, với i = 1, 2, 3, …, N), mỗi số cách nhau một ký tự khoảng trắng.

Dữ liệu ra: Ghi vào tập tin BAI01.OUT là một số duy nhất (Số lượng ngôi nhà nhìn thấy bãi biển).

Dữ liệu thử:

BAI01.INP	BAI01.OUT	Giải thích
`6` `7 6 8 9 12 11`	`2`	2 là số ngôi nhà nhìn thấy bãi biển (ngôi nhà có chiều cao là 12, 11)

Bài 2. Vị trí (6,0 điểm)

Xét dãy số sau:

Dãy số được tạo bằng cách: Dòng thứ i gồm i số tự nhiên liên tiếp bắt đầu từ i.

Ví dụ: 5 dòng đầu tiên tạo thành dãy:

1 2 3 3 4 5 4 5 6 7 5 6 7 8 9

Gọi dãy số trên là dãy D.

Yêu cầu: Viết chương trình tìm vị trí xuất hiện đầu tiên của số K trong dãy D.

Dữ liệu vào: Cho trong tập tin BAI02.INP một dòng duy nhất là số tự nhiên K (1 < K < 10¹⁰).

Dữ liệu ra: Ghi vào tập tin BAI02.OUT một số duy nhất (vị trí xuất hiện đầu tiên của số K trong dãy D).

Dữ liệu thử:

BAI02.INP	BAI02.OUT
`6`	`9`

Bài 3. Chuẩn hóa (6,0 điểm)

Một văn bản được gọi là văn bản chuẩn nếu đáp ứng các điều kiện sau:

Giữa hai từ liền nhau có duy nhất một ký tự khoảng trắng;
Dấu ngắt câu (dấu chấm, dấu phẩy, dấu chấm phẩy, dấu chấm hỏi, dấu chấm than) được đặt sát vào ký tự cuối của từ đứng trước nó, sau đó mới đến ký tự khoảng trắng;
Dấu mở ngoặc đơn, dấu mở ngoặc vuông và dấu mở ngoặc kép phải đặt ngay trước từ đầu tiên trong ngoặc, không có ký tự khoảng trắng giữa từ và dấu mở ngoặc;
Dấu đóng ngoặc đơn, dấu đóng ngoặc vuông và dấu đóng ngoặc kép phải đặt ngay sau từ cuối cùng trong ngoặc, không có ký tự khoảng trắng giữa từ và dấu đóng ngoặc.

Yêu cầu: Viết chương trình kiểm tra và đưa đoạn văn bản về dạng văn bản chuẩn theo các điều kiện trên.

Dữ liệu vào: Cho trong tập tin BAI03.INP gồm nhiều dòng, mỗi dòng không quá 255 kí tự.

Dữ liệu ra: Ghi vào tập tin BAI03.OUT là đoạn văn bản đã được chuẩn hóa từ dữ liệu trên.

Dữ liệu thử:

BAI03.INP	BAI03.OUT
`( Cham ngoan , hoc gioi )` `" [ Chao mung ] "" ngay 26 thang 03 " .`	`(Cham ngoan, hoc gioi)` `"[Chao mung]" "ngay 26 thang 03".`

Bài 4. Độ dài đoạn (5,0 điểm)

Độ dài đoạn là một đoạn gồm các số ngẫu nhiên (tăng, giảm tuỳ ý) trong dãy số theo thứ tự từ trái sang phải. Cho dãy N số nguyên dương (1 ≤ N ≤ 500).

Yêu cầu: Viết chương trình tìm độ dài đoạn con giảm dài nhất mà có tổng nhỏ nhất và in đoạn con đó (với |a[i]| > |a[i+1]|). Nếu có nhiều đoạn con bằng nhau thì in đoạn đầu tiên.

Dữ liệu vào: Cho trong tập tin BAI04.INP gồm nhiều dòng:

Dòng thứ nhất chứa số tự nhiên N (1 ≤ N ≤ 500).
Dòng thứ hai gồm N số nguyên (|a[i]| ≤ 1000, với i = 1, 2, 3, …, N), mỗi số cách nhau một ký tự khoảng trắng.

Dữ liệu ra: Ghi vào tập tin BAI04.OUT gồm 3 dòng:

Dòng 1: Độ dài đoạn con giảm dài nhất mà có tổng nhỏ nhất.
Dòng 2: Tổng nhỏ nhất của đoạn con giảm dài nhất.
Dòng 3: Đoạn con dài nhất theo yêu cầu trên, mỗi số cách nhau một ký tự khoảng trắng.

Dữ liệu thử:

BAI04.INP	BAI04.OUT	Giải thích
`9` `1 2 1 3 4 5 3 2 4`	`3` `10` `5 3 2`	3 là độ dài đoạn 10 là tổng các số trong đoạn con 5 3 2 là đoạn con
`9` `1 3 2 1 4 5 3 2 4`	`3` `6` `3 2 1`	3 là độ dài đoạn 6 là tổng các số trong đoạn con 3 2 1 là đoạn con

Ghi chú:

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. Ngôi nhà (3,0 điểm)

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

Hướng dẫn giải

Duyệt các ngôi nhà từ phải sang trái (từ phía biển vào) và giữ chiều cao lớn nhất đã gặp. Ngôi nhà hiện tại nhìn thấy biển khi nó cao hơn giá trị lớn nhất này, vì mọi nhà bên phải đã được gộp vào biến cực đại.

Độ 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;
    if (!(cin >> n))
        return 0;
    vector<int> a(n);
    for (int &x : a)
        cin >> x;
    int mx = -1, ans = 0;
    for (int i = n - 1; i >= 0; --i)
        if (a[i] > mx)
            ++ans, mx = a[i];
    cout << ans;
}

Bài 2. Vị trí (6,0 điểm)

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

Hướng dẫn giải

Dòng r chứa các giá trị từ r đến 2r − 1. Dòng đầu tiên chứa K là r = ⌈(K + 1)/2⌉. Trước dòng r có r(r − 1)/2 phần tử, còn K đứng ở vị trí thứ K − r + 1 trong dòng, nên đáp án là r(r − 1)/2 + K − r + 1.

Phép nhân trung gian có thể vượt 64 bit nên dùng __int128.

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

#include <bits/stdc++.h>
using namespace std;
using int64 = long long;
void print128(__int128 x) {
    if (x >= 10)
        print128(x / 10);
    cout << char('0' + x % 10);
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int64 k;
    cin >> k;
    /* Row r contains r..2r-1, hence the first possible row is ceil((k+1)/2). */
    int64 r = (k + 2) / 2;
    __int128 pos = (__int128)(r - 1) * r / 2 + (k - r) + 1;
    print128(pos);
}

Bài 3. Chuẩn hóa (6,0 điểm)

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

Hướng dẫn giải

Xử lý từng dòng, gom mọi chuỗi khoảng trắng liên tiếp thành một trạng thái “đang chờ khoảng trắng”:

Dấu câu và dấu đóng ngoặc được ghi sát vào từ đứng trước (bỏ khoảng trắng chờ).
Từ mới hoặc dấu mở ngoặc: ghi đúng một khoảng trắng trước nó, trừ khi ngay trước đó là dấu mở ngoặc.
Dấu ngoặc kép lần lượt được xem là mở, đóng, mở, đóng… (đếm số dấu " đã gặp).

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

#include <bits/stdc++.h>
using namespace std;
bool punct(char c) { return c == '.' || c == ',' || c == ';' || c == '?' || c == '!'; }
int quotes = 0; // số dấu " đã gặp: chẵn thì dấu " tiếp theo là mở, lẻ là đóng
string chuanHoa(const string &s) {
    string out;
    bool space = false;    // vừa gặp khoảng trắng (hoặc vừa đóng ngoặc/dấu câu)
    bool afterOpen = true; // ký tự vừa ghi là dấu mở ngoặc (hoặc đầu dòng)
    for (char c : s) {
        if (isspace((unsigned char)c)) {
            space = true;
            continue;
        }
        bool isOpen = (c == '(' || c == '[');
        bool isClose = (c == ')' || c == ']');
        if (c == '"') {
            isOpen = (quotes % 2 == 0);
            isClose = !isOpen;
            ++quotes;
        }
        if (punct(c) || isClose) {
            // dính vào từ đứng trước
            out += c;
            space = true;
            afterOpen = false;
        } else {
            // từ mới hoặc dấu mở ngoặc: cách một khoảng trắng, trừ khi ngay sau dấu mở ngoặc
            if (space && !afterOpen)
                out += ' ';
            out += c;
            space = false;
            afterOpen = isOpen;
        }
    }
    return out;
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    string line;
    while (getline(cin, line))
        cout << chuanHoa(line) << '\n';
}

Bài 4. Độ dài đoạn (5,0 điểm)

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

Hướng dẫn giải

Duyệt một lần, giữ đoạn hiện tại còn thỏa |a[i − 1]| > |a[i]| cùng độ dài và tổng của nó. Khi điều kiện bị phá, bắt đầu đoạn mới. Cập nhật đáp án khi đoạn dài hơn, hoặc cùng độ dài nhưng tổng nhỏ hơn; nếu hòa cả hai thì giữ đoạn 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;
    cin >> n;
    vector<long long> a(n);
    for (auto &x : a)
        cin >> x;
    int bestL = 0, bestLen = 1, cur = 0;
    long long curSum = a[0], bestSum = a[0];
    for (int i = 1; i < n; i++) {
        if (llabs(a[i - 1]) > llabs(a[i]))
            curSum += a[i];
        else
            cur = i, curSum = a[i];
        int len = i - cur + 1;
        if (len > bestLen || (len == bestLen && curSum < bestSum)) {
            bestLen = len;
            bestSum = curSum;
            bestL = cur;
        }
    }
    cout << bestLen << '\n' << bestSum << '\n';
    for (int i = bestL; i < bestL + bestLen; i++)
        cout << a[i] << (i + 1 == bestL + bestLen ? '\n' : ' ');
}

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