Học sinh giỏi 9 Cần Thơ 2023 - 2024¶

Bài 1: Chọn quà¶

Đề bài¶

Trong một buổi tri ân khách hàng, cửa hàng chuẩn bị $n$ phần quà. Phần quà thứ $i$ có giá trị là $a_i$. Bạn được phép chọn đúng $k$ phần quà trong $n$ phần quà trên.

Yêu cầu: hãy lập trình xác định tổng giá trị lớn nhất của $k$ phần quà có thể chọn.

Dữ liệu vào: CHONQUA.INP

Dòng đầu tiên ghi hai số nguyên dương $n, k (1 \le n \le 10^2, k \le n)$.
Dòng thứ hai ghi $n$ số nguyên dương, số thứ $i$ cho biết giá trị $a_i (a_i \le 10^3)$.

Kết quả: CHONQUA.OUT

Một số là kết quả tìm được.

Ví dụ:

CHONQUA.INP	CHONQUA.OUT
5 3 1 2 3 1 4	9

Bài giải đề xuất¶

Ý tưởng chính¶

Sắp xếp mảng A theo thứ tự giảm dần.

Tính tổng của k phần tử đầu tiên.

Viết chương trình¶

C++Python

    // Sắp xếp mảng A theo thứ tự giảm dần
    sort(A.begin(), A.end(), greater<int>());

    // Tính tổng k phần tử đầu
    Sum = accumulate(A.begin(), A.begin() + k, 0);

    # Sắp xếp mảng A theo thứ tự giảm dần
    A.sort(reverse=True)

    # Tính tổng k phần tử đầu
    Sum = sum(A[:k])

Mã nguồn¶

Code đầy đủ được đặt tại GitHub.

Bài 2: Tưới cây¶

Đề bài¶

Trong một thành phố có trồng rất nhiều cây xanh. Vào mùa hè, các cây cần phải được tưới nước để bảo đảm sức sống. Có $n$ cây được trồng trên tuyến đường từ A đến B. Một xe vận chuyển chở theo $k$ lít nước di chuyển từ A đến B để tiến hành tưới cho các cây này. Xe sẽ tưới một đoạn các cây liên tục trong $n$ cây trên, cây thứ $i$ phải được tưới đúng $a_i$ lít nước. Xe có thể chọn vị trí cây bất kỳ trong đoạn AB để bắt đầu tưới.

Yêu cầu: hãy lập trình để xác định số lượng nhiều nhất các cây liên tục được tưới.

Dữ liệu vào: TUOICAY.INP

Dòng đầu tiên ghi hai số nguyên dương $n, k (n \le 10^5, k \le 10^9)$ lần lượt là số lượng cây và số lít nước trên xe.
Dòng thứ hai ghi n số nguyên dương cho biết giá trị $a_i (a_i \le 10^9$)$ là số lít nước cần tưới cho cây thứ $i$.

Kết quả: TUOICAY.OUT

Một số là kết quả tìm được.

Ví dụ:

TUOICAY.INP	TUOICAY.OUT
5 7 3 2 3 1 4

Ràng buộc:

50% số test có $n \le 10^3$.
50% số test còn lại không có ràng buộc gì thêm.

Bài giải đề xuất¶

Ý tưởng chính¶

Sử dụng kỹ thuật cửa số trượt (sliding window).

Viết chương trình¶

C++Python

    int left = 0;

    // tổng số nước đã tưới
    int water = 0;

    // Duyệt từng vị trí trong mảng A
    for (int right = 0; right < n; ++right)
    {
        // Cộng dồn tổng số nước đã sử dụng
        water += A[right];

        // Thu hẹp cửa sổ nếu cần
        while (water > k && left <= right)
        {
            water -= A[left];
            left++;
        }

        // Cập nhật số lượng cây nhiều nhất được tưới
        if (water <= k)
        {
            max_count = max(max_count, right - left + 1);
        }
    }

    left = 0

    # tổng số nước đã tưới
    water = 0

    # Duyệt từng vị trí trong mảng A
    for right in range(n):
        # Cộng dồn tổng số nước đã sử dụng
        water += A[right]

        # Thu hẹp cửa sổ nếu cần
        while water > k and left <= right:
            water -= A[left]
            left += 1

        # Cập nhật số lượng cây nhiều nhất được tưới
        if water <= k:
            max_count = max(max_count, right - left + 1)

Mã nguồn¶

Code đầy đủ được đặt tại GitHub.

Bài 3: Mật thư¶

Đề bài¶

Để mã hoá nội dung bức thư của mình, An thực hiện lần lượt các bước sau:

Dùng một trong hai chữ số 1 và 2 đặt trước từng từ mình viết.
Nếu phía trước từ đó là chữ số 1 thì nội dung từ đó được viết xuôi bình thường. Nếu phía trước từ đó là chữ số 2 thì nội dung từ đó được viết ngược lại.
Xoá hết tất cả dấu cách có trong bức thư.

Yêu cầu: hãy lập trình giải mã nội dung bức thư trên.

Dữ liệu vào: MATTHU.INP

Dòng đầu tiên ghi một số nguyên dương $n (n \le 10^5)$ là độ dài nội dung đã mã hoá.
Dòng thứ hai ghi nội dung của bức thư gồm các ký tự 'a'..'z', '1' và '2'.

Kết quả: MATTHU.OUT

Nội dung tìm được sau khi giải mã bức thư. Trong đó mỗi từ cách nhau đúng một khoảng trắng.

Ví dụ:

MATTHU.INP	MATTHU.OUT
17 1chuc2nab2iht1tot	chuc ban thi tot

Bài giải đề xuất¶

Ý tưởng chính¶

Nếu gặp một chữ cái, ta thêm nó vào biến tạm word (dùng để lưu một từ).

Nếu gặp chữ '1' hoặc '2':

Chữ số này báo hiệu kết thúc của từ word vừa tạo trên.
word này phải được xử lý (giữ nguyên hoặc đảo ngược) dựa trên biến digit đã được lưu từ trước đó, tức chữ số đứng trước word trong chuỗi đầu vào (tạm đặt là encoded).
Sau khi xử lý word, chữ số mà ta vừa gặp (encoded[i]) chính là chữ số điều khiển cho từ tiếp theo sẽ được hình thành. Vì vậy, ta phải cập nhật chữ số mới này vào biến digit để khi word tiếp theo hoàn thành, ta biết phải xử lý nó như thế nào.

Viết chương trình¶

Bước 0:

Viết hàm đảo ngược chuỗi, dùng cho trường hợp gặp chữ số '2'.

C++Python

string reverse_string(string s)
{
    reverse(s.begin(), s.end());
    return s;
}

def reverse_string(s):
    return s[::-1]

Bước 1:

Duyệt từng ký tự của chuỗi đầu vào encoded và xử lý.

C++Python

    string word = "";
    char digit = ' '; // ký tự khoảng trắng

    // Duyệt từng ký tự trong chuỗi encoded
    for (int i = 0; i < n; ++i)
    {
        // Nếu ký tự đang xét là 1 hoặc 2
        if (encoded[i] == '1' || encoded[i] == '2')
        {
            // Nếu word hiện hành khác rỗng
            if (!word.empty())
            {
                // thì giữ nguyên hoặc đảo chuỗi
                if (digit == '1')
                    decoded += word;
                else if (digit == '2')
                    decoded += reverse_string(word);

                // Nếu decoded khác rỗng thì thêm ký tự khoảng trắng
                if (!decoded.empty())
                    decoded += " ";

                // Khởi tạo lại word rỗng
                word = "";
            }

            digit = encoded[i];
        }
        else
        {
            // Ngược lại, nếu không phải ký tự số thì ghép ký tự đang xét vào word
            word += encoded[i];
        }
    }

    word = ''
    digit = ' ' # ký tự khoảng trắng

    # Duyệt từng ký tự trong chuỗi encoded
    for i in range(n):
        # Nếu ký tự đang xét là 1 hoặc 2
        if encoded[i] == '1' or encoded[i] == '2':
            # Nếu word hiện hành khác rỗng
            if word:
                # thì giữa nguyên hoặc đảo chuỗi
                if digit == '1':
                    decoded += word
                elif digit == '2':
                    decoded += reverse_string(word)

                # Nếu decoded khác rỗng thì thêm ký tự khoảng trắng
                if decoded:
                    decoded += ' '

                # Khởi tạo word rỗng
                word = ''

            digit = encoded[i]

        else:
            # Ngược lại, nếu không phải ký tự số thì ghép ký tự đang xét vào word
            word += encoded[i]

Bước 2:

Xử lý từ cuối cùng:

Sau khi vòng lặp trên kết thúc, vẫn còn word cuối cùng chưa được xử lý.

Dựa trên digit tương ứng, ta thực hiện tương tự như trong vòng lặp để thêm từ cuối cùng vào biến kết quả decoded.

Loại bỏ dấu cách thừa (nếu có):

Kiểm tra xem decoded có rỗng không và ký tự cuối cùng có phải là dấu cách không. Nếu có, loại bỏ nó. Đây là thao tác mang tính phòng hờ.

C++Python

    // Xử lý từ cuối cùng
    if (!word.empty())
    {
        if (digit == '1')
            decoded += word;
        else if (digit == '2')
            decoded += reverse_string(word);
    }

    // Loại bỏ ký tự khoảng trắng ở cuối nếu có
    if (!decoded.empty() && decoded.back() == ' ')
        decoded.pop_back();

    # Xử lý từ cuối cùng
    if word:
        if digit == '1':
            decoded += word
        elif digit == '2':
            decoded += reverse_string(word)

    # Loại bỏ ký tự khoảng trắng ở cuối nếu có
    if decoded and decoded[-1] == ' ':
        decoded = decoded[:-1]

Mã nguồn¶

Code đầy đủ được đặt tại GitHub.

Bài 4: Bảng số¶

Đề bài¶

Cho một bảng số gồm n x n ô và một số nguyên dương $k$. Tại một ô giao nhau giữa hàng $i (1 \le i \le n)$ và cột $j (1 \le j \le n)$ có giá trị bằng $i \times j$.

Ví dụ: n = 5, ta có bảng sau:

1 2 3 4 5
2 4 6 8 10
3 6 9 12 15
4 8 12 16 20
5 10 15 20 25

Yêu cầu: hãy lập trình tìm số lần xuất hiện của giá trị $k$ trong bảng số trên.

Dữ liệu vào: BANGSO.INP

Một dòng duy nhất chứa hai số nguyên dương $n, k (n \le 10^6, k \le 10^{12})$.

Kết quả: BANGSO.OUT

Một số là kết quả tìm được.

Ví dụ:

BANGSO.INP	BANGSO.OUT
5 3	2

Ràng buộc:

50% số test có $n \le 10^3, k \le n^2$.
50% số test còn lại không có ràng buộc gì thêm.

Bài giải đề xuất¶

Ý tưởng chính¶

Ta nhận thấy trong mỗi hàng i, các phần tử đều bộ bội của phần tử đầu hàng, cũng chính là i.

Do đó, ta có thể duyệt qua từng hàng i và xét xem k có phải là bội của i hay không. Nếu có thì tăng biến đếm count lên 1.

Viết chương trình¶

C++Python

    // Duyệt từng chỉ số hàng trong đoạn [1..n]
    for (lli i = 1; i < n + 1; ++i)
    {
        // Nếu k không chia hết cho i thì không
        if (k % i != 0) continue;

        // Tính giá trị cột j
        lli j = k / i;

        // Kiểm tra xem j có nằm trong phạm vi của bảng không (1 <= j <= n)
        if (j <= n) count++;
    }

    # Duyệt từng chỉ số hàng trong đoạn [1..n]
    for i in range(1, n):
        # Nếu k không chia hết cho i thì không
        if k % i != 0:
            continue

        # Tính giá trị cột j
        j = k // i

        # Kiểm tra xem j có nằm trong phạm vi của bảng không (1 <= j <= n)
        if j <= n:
            count += 1

Mã nguồn¶

Code đầy đủ được đặt tại GitHub.

Bao tôi ly cafe 🧋 nhé!