2025 - 2026 Lâm Đồng

Bài 1: Xâu con

Đề bài

Anny là một người rất đam mê khám phá, tình cờ Anny có được một tấm bản đồ kho báu.

Trong hành trình tìm kiếm, Anny tìm được cửa kho báu thứ nhất. Trên cửa có ghi một dãy ký tự tiếng Anh in thường liên tiếp nhau. Bản đồ kho báu cho biết mật mã để mở cửa lần này là số lượng xâu con đặc biệt của dãy ký tự trên.

Biết rằng, một xâu con đặc biệt là một dãy ký tự liên tiếp bắt đầu bằng một nguyên âm ('a', 'e', 'i', 'o', 'u') và kết thúc bằng một phụ âm hoặc ngược lại.

Yêu cầu: Hãy giúp Anny đếm số lượng xâu con đặc biệt của xâu ký tự trên cửa.

Đầu vào: XAUCON.INP

Gồm một dòng duy nhất chứa dãy ký tự.

Đầu ra: XAUCON.OUT

Gồm một số nguyên duy nhất là mật mã tìm được.

Ví dụ:

XAUCON.INP	XAUCON.OUT
abco	4

Ràng buộc:

• Có 50% số test ứng với 50% số điểm có chiều dài xâu \(\le 10^3\).
• Có 50% số test ứng với 50% số điểm có chiều dài xâu \(\le 5 \times 10^5\).

Cách giải đề xuất

Ý tưởng chính

Với một cặp bất kỳ gồm nguyên âm v và phụ âm c, ta đều vẽ được một và chỉ một đoạn thẳng nối chúng, dù v nằm trước c hay c nằm trước v.

Mỗi cặp v và c như thế đều hình thành một chuỗi con đặc biệt.

Vậy số lượng chuỗi con đặc biệt được tính bằng: tích của số nguyên âm và số phụ âm có trong chuỗi.

Viết chương trình

1. Viết hàm is_vowel() dùng để kiểm ký tự là nguyên âm hay phụ âm.

C++Python

bool is_vowel(char c)
{
    return c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u';
}

def is_vowel(c):
    return c == 'a' or c == 'e' or c == 'i' or c == 'o' or c == 'u'

2. Dùng vòng lặp để đếm số nguyên âm và số phụ âm. Sau đó, tính tích để ra được số chuỗi con đặc biệt.

C++Python

void process()
{
    int vowel = 0;
    int consonant = 0;

    // Duyệt chuỗi để đếm số nguyên âm và số phụ âm
    for (int i = 0; i < s.length(); ++i)
    {
        if (is_vowel(s[i]))
            ++vowel;
        else
            ++consonant;
    }

    // Tính số chuỗi con đặc biệt
    result = vowel * consonant;
}

def process():
    global s, result

    vowel = 0
    consonant = 0

    # Duyệt chuỗi để đếm số nguyên âm và số phụ âm
    for i in range(len(s)):
        if is_vowel(s[i]):
            vowel += 1
        else:
            consonant += 1

    # Tính số chuỗi con đặc biệt
    result = vowel * consonant

Mã nguồn

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

---

Bài 2: Cạm bẫy

Đề bài

Sau khi mở được cửa thứ nhất của kho báu, Anny cần vượt qua một chướng ngại vật để mở cửa thứ hai. Chướng ngại vật lần này là một ma trận các số nguyên dương không vượt quá \(10^9\) có chứa các cạm bẫy.

Bản đồ kho báu mô tả ma trận gồm \(N\) hàng và \(M\) cột. Cạm bẫy được đặt trên các hàng và các cột có chứa giá trị lớn nhất hoặc nhỏ nhất của ma trận.

Mật mã để mở cửa thứ hai của kho báu là số lượng ô của ma trận không chứa cạm bẫy.

Yêu cầu: Hãy giúp Anny đếm số ô của ma trận không chứa cạm bẫy.

Đầu vào: CAMBAY.INP

• Dòng đầu gồm hai số nguyên dương \(N\) và \(M\) được viết cách nhau một ký tự khoảng trắng.
• \(N\) dòng tiếp theo, mỗi dòng gồm \(M\) số nguyên, các số được viết cách nhau một ký tự khoảng trắng.

Đầu ra: CAMBAY.OUT

Gồm một số duy nhất là mật mã tìm được.

Ví dụ:

CAMBAY.INP	CAMBAY.OUT
2 3 5 4 3 2 4 2 1 2 3 4 1 2 3 4 4 3 4 2	4

Ràng buộc:

• Có 40% số test ứng với 40% số điểm có: \(1 \le N, M \le 10\).
• Có 30% số test ứng với 30% số điểm có: \(1 \le N, M \le 100\).
• Có 30% số test ứng với 30% số điểm có: \(1 \le N \times M \le 5 \times 10^6\).

Cách giải đề xuất

Ý tưởng chính

1. Gọi matrix là ma trận đầu vào.

• Ràng buộc \(1 \le N \times M \le 5 \times 10^6\) chỉ cho biết tổng số ô của ma trận, chứ không cho biết rõ giới hạn của riêng \(N\) hoặc \(M\). Điều này có thể tạo ra các tình huống như sau:

  • Ma trận vuông với \(N = M \simeq 2300\).
  • \(N = 1\) và \(M = 5,000,000\)
  • \(N = 5,000,000\) và \(M = 1\)

  Nếu ta khai báo dạng matrix[MAX][MAX] thì phải chọn MAX đủ lớn để bao quát các trường hợp, cụ thể là matrix[5000000][5000000].

  Với mỗi int chiếm 4 byte, mảng trên chiếm đến 91 terabtye: không khả thi.

• Nếu dùng mảng động hai chiều vector<vector<int>> matrix thì sẽ tốn thời gian tìm địa chỉ bộ nhớ khi nhảy từ hàng này sang hàng khác. Do vector<vector<int>> thực chất là một vector chứa các con trỏ trỏ đến các vector khác nằm rải rác trong bộ nhớ.

Vì vậy, thay vì tổ chức mảng hai chiều, ta nên tổ chức matrix thành mảng động một chiều, cụ thể: vector<int> matrix.

2. Để chuyển đổi từ hai chiều thành một chiều, ta áp dụng công thức tính chỉ số của phần tử là: i = r * m + c, trong đó:

• i là chỉ số của phần tử trong matrix.
• r và c là chỉ số dùng để duyệt theo số hàng n và số cột m của dữ liệu đầu vào.
• m là số cột của dữ liệu đầu vào.

3. Dùng hai mảng một chiều trap_rows và trap_cols để đánh dấu hàng và cột có dính bẫy, trong đó có bẫy là true, không có bãy là false.

4. Số ô không chứa bẫy là tính của số ô false trong trap_rows và số ô false trong trap_cols.

Viết chương trình

1. Đọc dữ liệu đầu vào và chuyển đổi luôn thành mảng một chều matrix. Đồng thời, xác định giá trị nhỏ nhất min_value và lớn nhất max_value.

C++Python

    cin >> n >> m;

    matrix.resize(n * m, 0);

    // Đọc dữ liệu và chuyển đổi luôn sang mảng một chiều
    for (int r = 0; r < n; ++r)
    {
        for (int c = 0; c < m; ++c)
        {
            int i = r * m + c;
            cin >> matrix[i];

            // Tìm giá trị nhỏ nhất
            if (matrix[i] < min_value)
                min_value = matrix[i];

            // Tìm giá trị lớn nhất
            if (matrix[i] > max_value)
                max_value = matrix[i];
        }
    }

    d# Đọc toàn bộ dữ liệu vào bộ nhớ đệm và tách thành các token
    input_data = sys.stdin.read().split()

    iterator = iter(input_data)

    n = int(next(iterator))
    m = int(next(iterator))

    total_elements = n * m
    matrix = [0] * total_elements

    # Đọc dữ liệu và chuyển đổi luôn sang mảng một chiều
    for i in range(total_elements):
        value = int(next(iterator))
        matrix[i] = value

        # Tìm giá trị nhỏ nhất
        if value < min_value:
            min_value = value

        # Tìm giá trị lớn nhất
        if value > max_value:
            max_value = value

2. Viết hàm process() dùng để tính kết quả đầu ra như sau:

• Khởi tạo mảng trap_rows và trap_cols chứa toàn giá trị false.

• Dùng vòng lặp cho r chạy đến n, c chạy đến m:

  • Lấy ra phần tử của matrix mà tương ứng với hàng r và cột c của dữ liệu đầu vào.
  • Nếu phần tử này bằng giá trị nhỏ nhất hoặc lớn nhất thì đánh dấu true trong mảng trap_rows và trap_cols.
  • Tính tích các ô false trong trap_rows và trap_cols.

C++Python

void process()
{
    vector<bool> trap_rows(n, false);
    vector<bool> trap_cols(m, false);

    int value;

    for (int r = 0; r < n; ++r)
    {
        for (int c = 0; c < m; ++c)
        {
            // Lấy ra giá trị tại hàng r, cột c
            value = matrix[r * m + c];

            if (value == min_value || value == max_value)
            {
                // Nếu giá trị lấy ra bằng nhỏ nhất hoặc lớn nhất
                // thì đánh dấu hàng r, cột c có bẫy
                trap_rows[r] = true;
                trap_cols[c] = true;
            }
        }
    }

    // Đếm số hàng không có bẫy
    int no_trap_row_count = count(trap_rows.begin(), trap_rows.end(), false);

    // Đếm số cột không có bẫy
    int no_trap_col_count = count(trap_cols.begin(), trap_cols.end(), false);

    result = no_trap_row_count * no_trap_col_count;
}

def process():
    global n, m , matrix, result

    trap_rows = [False] * n
    trap_cols = [False] * m

    for r in range(n):
        for c in range(m):
            i = r * m + c

            # Lấy ra giá trị tại hàng r, cột c
            value = matrix[i]

            if value == min_value or value == max_value:            
                # Nếu giá trị lấy ra bằng nhỏ nhất hoặc lớn nhất
                # thì đánh dấu hàng r, cột c có bẫy
                trap_rows[r] = True
                trap_cols[c] = True

    # Đếm số hàng không có bẫy
    no_trap_row_count = trap_rows.count(False)

    # Đếm số cột không có bẫy
    no_trap_col_count = trap_cols.count(False)

    result = no_trap_row_count * no_trap_col_count

Mã nguồn

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

---

Bài 3. Mật mã

Đề bài

Sau khi qua cửa thứ hai, Anny gặp được cánh cửa thứ ba.

Để mở cửa Anny cần có mật mã. Mật mã lần này là chữ số cuối cùng của phép toán a" được ghi trên bản đồ kho báu.

Yêu cầu: Hãy giúp Anny tìm chữ số cuối cùng của phép toán \(a^n\).

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

Gồm hai số nguyên dương \(a\) và \(n\) được viết cách nhau một ký tự khoảng trắng.

Đầu ra: MATMA.OUT

Gồm một số duy nhất là mật mã tìm được.

Ví dụ:

MATMA.INP	MATMA.OUT
25	2

Ràng buộc:

• Có 40% số test ứng với 40% số điểm có: \(1 \le a \le 9; 1 \le n \lt 10^3\)
• Có 30% số test ứng với 30% số điểm có: \(1 \le a \le 10^6; 1 \le n \le 10^6\).
• Có 30% số test ứng với 30% số điểm có: \(1 \le a \le 10^9; 1 \le n \le 10^18\).

Cách giải đề xuất

Ý tưởng chính

1. Cách 1: áp dụng cách tính luỹ thừa nhị phân (binary exponentiation).

Thay vì nhân n lần, ta lặp thao tác bình phương cơ số a và nhân nó vào kết quả bất cứ khi nào số mũ hiện hành là lẻ. Cụ thể:

Lặp các thao tác:

• Nếu số mũ n là lẻ thì nhân a vào kết quả (biến result được khởi tạo là 1).

  Ngược lại, nếu chẵn thì thôi.

• Bình phương a.

• Chia đôi số mũ n.

Vòng lặp dừng khi không thể chia đôi n được nữa.

Ví dụ:

a	n	n là chẵn hoặc lẻ	Kết quả
2	5	5 là lẻ	1
4	2	2 là chẵn	2
16	1	1 là lẻ	2
256	0	dừng vòng lặp	32

Với \(n = 10^{18}\), vòng lặp trên thực hiện khoảng 60 lần, vì \(2^60 \simeq 10^{18}\).

1. Cách 2: áp dụng tính chất toán học chu kỳ của chữ số tận cùng.

Chữ số tận cùng của \(a^n\) sẽ lặp lại theo chu kỳ tối đa là 4. Cụ thể:

Số cuối của a	Mũ 1	Mũ 2	Mũ 3	Mũ 4	Mũ 5 (Lặp lại)	Chu kỳ thực
1	1	1	1	1	1	1
2	2	4	8	6	2	4
3	3	9	7	1	3	4
4	4	6	4	6	4	2
5	5	5	5	5	5	1
6	6	6	6	6	6	1
7	7	9	3	1	7	4
8	8	4	2	6	8	4
9	9	1	9	1	9	2

Theo bảng trên, ta có 3 nhóm:

• Nhóm chu kỳ 1, tức bất biến: 0, 1, 5, 6
• Nhóm chu kỳ 2, tức dao động: 4, 9
• Nhóm chu kỳ 4: 2, 3, 7, 8

Vì 4 là bội chung nhỏ nhất của 1, 2 và 4 nên thay vì mũ n, ta sẽ mũ k với: k = (n - 1) % 4 + 1. Đây là công thức tổng quát nhất.

Viết chương trình

1. Cách 1:

C++Python

void process_1()
{
    // Mod 10 để lấy chữ số cuối của a
    a %= 10;

    // Trong khi số mũ n vẫn còn chia đôi được
    while (n > 0)
    {
        if (n & 1)
        {
            // Nếu số mũ lẻ thì chỉ nhân thêm cơ số a vào
            result = (result * a) % 10;
        }

        // Ngược lại, nếu số mũ chẵn thì bình phương cơ số a lên
        a = (a * a) % 10;

        // Chia đôi số mũ
        n >>= 1;
    }
}

def process_1():
    global a, n, result

    # Mod 10 để lấy chữ số cuối của a
    a %= 10

    # Trong khi số mũ n vẫn còn chia đôi được
    while n > 0:
        if n & 1:        
            # Nếu số mũ lẻ thì chỉ nhân thêm cơ số a vào
            result = (result * a) % 10

        # Ngược lại, nếu số mũ chẵn thì bình phương cơ số a lên
        a = (a * a) % 10

        # Chia đôi số mũ
        n >>= 1

2. Cách 2:

C++Python

void process_2()
{
    // Mod 10 để lấy chữ số cuối của a
    a %= 10;

    // Ánh xạ số mũ n thành số mũ k
    lli k = (n - 1) % 4 + 1;

    result = (lli)pow(a, k) % 10;
}

def process_2():
    global a, n, result

    # Mod 10 để lấy chữ số cuối của a
    a %= 10

    # Ánh xạ số mũ n thành số mũ k
    k = (n - 1) % 4 + 1

    result = pow(a, k) % 10

Mã nguồn

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

---

Bài 4. Du lịch

Đề bài

Sau khi tìm được kho báu, Anny sắp xếp một chuyến đi du lịch vòng quanh thế giới.

Có \(N\) điểm du lịch Anny muốn ghé thăm, được đánh số từ \(1\) đến \(N\). Giữa các điểm du lịch có các chuyến bay đi trực tiếp; chi phí để bay từ điểm \(i\) đến điểm \(j\) là \(C_{ij}\) (có thể khác \(C_{ji}\)) và \(1 \le C_{ij} \le 10^9\).

Anny muốn chọn một hành trình du lịch qua \(N\) điểm, mỗi điểm chỉ ghé thăm một lần duy nhất. Với tinh thần tiết kiệm, Anny muốn chọn một hành trình du lịch với tổng chi phí nhỏ nhất.

Yêu cầu: Hãy giúp Anny tìm được hành trình có tổng chi phí nhỏ nhất.

Đầu vào: DULICH.INP

• Dòng đầu ghi số nguyên dương \(N\).
• Dòng thứ \(i\) trong \(N\) dòng tiếp theo, ghi \(N\) số nguyên không âm \(C_{ij}\) là chi phí bay từ điểm \(i\) đến điểm \(j (1 \le j \le n)\).

Đầu ra: DULICH.OUT

Gồm một số nguyên dương duy nhất là tổng chi phí của hành trình nhỏ nhất tìm được.

Ví dụ:

DULICH.INP	DULICH.OUT
6 0 1 2 1 3 4 5 0 3 2 3 4 4 1 0 2 1 2 4 2 5 0 4 3 2 5 3 5 0 2 5 4 3 3 1 0	8

Ràng buộc:

• Có 50% số test ứng với 50% số điểm có: \(5 \lt n \le 10\).
• Có 50% số test ứng với 50% số điểm có: \(10 \lt n \le 15\).

Cách giải đề xuất

Ý tưởng chính

Sử dụng quy hoạch động trạng thái (bitmask dynamic programming). Cụ thể:

1. Ta dùng một biến nguyên, đặt là mask, biểu diễn các địa điểm đã ghé thăm dưới dạng nhị phân.

Ví dụ:
Với n = 6, mask = 5 nghĩa là đã ghé thăm các điểm 0 và 2, vì biểu diễn nhị phân của 5 là 000101.

2. Gọi d[mask][u] là tổng chi phí nhỏ nhất để đi qua các địa điểm trong mask và kết thúc tại điểm u.

Lưu ý: u được đánh từ 0, thay vì từ 1 như đề bài.

Như vậy, ta có:

• Trang thái ban đầu:

  Với mọi điểm u, chi phí để ghé thăm chính nó là 0: d[1 << u][u] = 0

• Thay đổi trạng thái:

  Đang đứng ở điểm u, ta thử đi tiếp đến v: d[mask | (1 << v)][v] = min(d[mask | (1 << v)][v], d[mask][u] + c[u][v])

3. Sau khi đã điền xong các giá trị cho mảng d, thì kết quả output là giá trị nhỏ nhất tính trong số các trạng thái "full mask", tức đã ghé thăm đủ các địa điểm: min(d[(1 << n) - 1][u]), với mọi u.

Hướng tiếp cận trên có độ phức tạp khoảng \(O(2^n \cdot n^2)\). Với \(n = 15\), \(2^15 \cdot 15^2 = 32768 \times 22 \approx 7.3 \times 10^6\) phép tính, dư sức chạy trong 1 giây.

Ngoài ra, với subtask nhỏ (\(n \le 10\)), ta có thể dùng phương pháp quay lui và kỹ thuật nhánh cận.

Độ phức tạp của quay lui là \(O(n!)\). Với \(n \le 10\), \(10! = 1 \times 2 \times \dots \times 10 = \mathbf{3,628,800}\), dư sức chạy trong 1 giây.

Viết chương trình

1. Khai báo các biến liên quan.

C++Python

typedef long long int lli;

const lli INF = 1e18;

int n;
int c[15][15];

// Khai báo mảng hai chiều d gồm 2^15 hàng, 15 cột
// d[mask][u] lưu chi phí nhỏ nhất đi qua các điểm trong mask, kết thúc tại điểm u
lli d[1 << 15][15];

// tổng chi phí nhỏ nhất, dùng để output
lli result = INF;

INF = float('inf')

n = 0
c = []

# Khai báo mảng hai chiều d gồm 2^15 hàng, 15 cột
# d[mask][u] lưu chi phí nhỏ nhất đi qua các điểm trong mask, kết thúc tại điểm u
d = []

# tổng chi phí nhỏ nhất, dùng để output
result = INF

2. Khởi tạo mảng d dùng cho quy hoạch động.

C++Python

    // Khởi tạo mảng d gồm toàn giá trị vô cực
    for (int mask = 0; mask < (1 << n); ++mask)
    {
        for (int v = 0; v < n; ++v)
        {
            d[mask][v] = INF;
        }
    }

    // Khởi tạo chi phí 0 cho các điểm xuất phát
    for (int v = 0; v < n; ++v)
    {
        d[1 << v][v] = 0;
    }

    # Khởi tạo mảng d gồm toàn giá trị vô cực
    d = [[INF] * n for _ in range(1 << n)]    

    # Khởi tạo chi phí 0 cho các điểm xuất phát
    for v in range(n):
        d[1 << v][v] = 0

3. Thực hiện quy hoạch động.

C++Python

    // Duyệt tất cả các trạng thái của mask
    for (int mask = 1; mask < (1 << n); ++mask)
    {
        // Duyệt từng điểm u đang đứng
        for (int u = 0; u < n; ++u)
        {
            // Kiểm tra xem u có nằm trong mask hay không
            if (mask & (1 << u))
            {
                // Kiểm tra xem có đường đi tới u hay không
                if (d[mask][u] == INF)
                    continue;

                // Duyệt điểm v chưa có trong mask, tức thử đi từ u đến v
                for (int v = 0; v < n; ++v)
                {
                    // Nếu chưa ghé thăm điểm v
                    if (!(mask & (1 << v)))
                    {
                        // Đánh dấu v đã được ghé thăm
                        int next_mask = mask | (1 << v);

                        // Tính tổng chi phí mới
                        lli new_cost = d[mask][u] + c[u][v];

                        // Cập nhật chi phí nhỏ hơn
                        if (new_cost < d[next_mask][v])
                        {
                            d[next_mask][v] = new_cost;
                        }
                    }
                }
            }
        }
    }

    # Duyệt tất cả các trạng thái của mask
    for mask in range(1, 1 << n):
        # Duyệt từng điểm u đang đứng
        for u in range(n):
            # Kiểm tra xem u có nằm trong mask hay không
            if mask & (1 << u):

                # Kiểm tra xem có đường đi tới u hay không
                if d[mask][u] == INF:
                    continue

                # Duyệt điểm v chưa có trong mask, tức thử đi từ u đến v
                for v in range(n):
                    # Nếu chưa ghé thăm điểm v
                    if not mask & (1 << v):
                        # Đánh dấu v đã được ghé thăm
                        next_mask = mask | (1 << v)

                        # Tính tổng chi phí mới
                        new_cost = d[mask][u] + c[u][v]

                        # Cập nhật chi phí nhỏ hơn
                        if new_cost < d[next_mask][v]:
                            d[next_mask][v] = new_cost

4. Tìm tổng chi phí nhỏ nhất.

C++Python

    // Tìm giá trị nhỏ nhất của tất cả các trạng thái full mask, tức mask = 11...1
    int full_mask = (1 << n) - 1;

    for (int v = 0; v < n; ++v)
    {
        if (d[full_mask][v] < result)
        {
            result = d[full_mask][v];
        }
    }

    # Tìm giá trị nhỏ nhất của tất cả các trạng thái full mask, tức mask = 11...1
    full_mask = (1 << n) - 1

    for v in range(n):    
        if d[full_mask][v] < result:
            result = d[full_mask][v]

Mã nguồn

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

Tags

Bao tôi ly cafe 🧋 nhé!