Học sinh giỏi 9 Cà Mau 2023 - 2024¶

Bài 1: Đếm ký tự¶

Đề bài¶

Xâu là dãy liên tiếp các ký tự, bao gồm chữ Latin, chữ số và dấu cách.

Yêu cầu: Cho xâu \(S\) có \(N\) ký tự chỉ chứa ký tự chữ Latin và in thường. Hãy đếm số lần xuất hiện của các ký tự có trong xâu \(S\).

Dữ liệu vào: demkitu.inp

Gồm một dòng duy nhất chứa xâu \(S\) có \(N\) ký tự \((1 \le N \le 10^6)\).

Dữ liệu ra: demkitu.out

Gồm nhiều dòng, mỗi dòng gồm hai kết quả lần lượt là ký tự và số lần xuất hiện của nó trong xâu S, ngăn cách nhau bởi một một khoảng trắng. Các ký tự được sắp xếp theo thứ tự alphabet.

Ví dụ:

demkitu.inp	demkitu.out
dbakabk	a 2 b 2 d 1 k 2

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

Ý tưởng chính¶

Sử dụng mảng tần số f để ghi nhận số lần xuất hiện của mỗi ký tự.

Lợi ích của mảng tần số f:

Hiệu quả về bộ nhớ.
Khi thực hiện đếm, chỉ cần một vòng lặp.
Tốc độ truy xuất là \(O(1)\) khi cập nhật số lần xuất hiện của một ký tự.
Dễ dàng xuất kết quả theo thứ tự bảng chữ cái.

Viết chương trình¶

Bước 1:

Khởi tạo mảng tần số f gồm 26 phần tử (ứng với 26 ký tự từ a đến z), mang giá trị 0, tức chưa xuất hiện lần nào.

C++Python

int f[26] = {};

f = [0] * 26

Bước 2:

Duyệt từng ký tự trong chuỗi và cập nhật số lần xuất hiện của nó vào mảng f.

C++Python

    // Duyệt từng ký tự của chuỗi s
    for (int i = 0; i < s.length(); i++)
    {
        // Ứng với ký tự s[i], cập nhật số lần xuất hiện của nó
        f[s[i] - 'a']++;
    }

    # Duyệt từng ký tự của chuỗi s
    for i in range(len(s)):
        # vỨng với ký tự s[i], cập nhật số lần xuất hiện của nó
        f[ord(s[i]) - ord('a')] += 1

Mã nguồn¶

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

Bài 2: Trò chơi¶

Đề bài¶

Có tất cả m câu hỏi và n đội chơi tham gia. Câu hỏi thứ \(i (1 \le i \le m)\), đội thứ \(j (1 \le j \le n)\) sẽ được ban giám khảo cho điểm là \(a_{ij}\).

Sau trò chơi, đội chiến thắng là đội có tổng số điểm của m câu hỏi là cao nhất.

Yêu cầu: Hãy giúp ban tổ chức tìm ra đội chiến thắng và tổng số điểm của đội đó.

Dữ liệu vào: trochoi.inp

Dòng đầu chứa hai số nguyên \(m, n (1 \le m, n \le 10^3)\).
\(m\) dòng sau, mỗi dòng chứa \(n\) số nguyên \(a_{ij}\) (1 \le \(a_{ij}\) \le 10^6) thể hiện số điểm câu hỏi thứ \(i\) của đội thứ \(j\), các số được ngăn cách nhau bởi một khoảng trắng.

Dữ liệu vào bảo đảm chỉ có duy nhất một đội chiến thắng.

Dữ liệu ra: trochoi.out

Gồm một dòng duy nhất chứa hai số nguyên lần lượt là số thứ tự và tổng số điểm của đội chiến thắng.

Ví dụ:

trochoi.inp	trochoi.out
4 5 2 5 4 1 2 4 6 7 3 3 6 9 5 4 3 3 8 1 2 4	2 28

Giải thích:

Có 4 câu hỏi và 5 đội chơi.
Số điểm 4 câu hỏi của đội 1 lần lượt là 2, 4, 6 và 3. Tổng điểm là 15.
Tương tự, tổng số điểm của đội 2, đội 3, đội 4 và đội 5 lần lượt là: 28, 17, 10 và 12.

Đội 2 là đội chiến thắng với 28 điểm.

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

Ý tưởng chính¶

Mỗi dòng trong input là điểm của các đội trong cùng một câu hỏi.

Cho nên, ta dùng mảng total để lưu tổng điểm của từng đội, với total[i] là tổng điểm của đội i. Ứng với mỗi dòng đọc vào, ta cộng dồn điểm vào total[i].

Duyệt mảng total, ta tìm được điểm cao nhất.

Viết chương trình¶

Bước 1:

Vừa đọc vừa cập nhật mảng total.

C++Python

    cin >> number_of_questions >> number_of_teams;

    // Khởi tạo mảng lưu tổng điểm của mỗi đội
    total.resize(number_of_teams, 0);

    int score;

    // Duyệt từng câu hỏi (từng hàng)
    for (int q = 0; q < number_of_questions; ++q)
    {
        // Duyệt từng đội (từng cột)
        for (int t = 0; t < number_of_teams; ++t)
        {
            cin >> score;

            // Cộng dồn điểm cho từng đội
            total[t] += score;
        }
    }

    with open(input_file, 'r') as f:
        number_of_questions, number_of_teams = map(int, f.readline().split())

        # Khởi tạo mảng lưu tổng điểm của mỗi đội
        total = [0] * number_of_teams

        # Duyệt từng câu hỏi (từng hàng)
        for q in range(number_of_questions):
            line = f.readline().split()

            # Duyệt từng đội (từng cột)
            for t in range(number_of_teams):
                score = int(line[t])

                # Cộng dồn điểm cho từng đội
                total[t] += score

Bước 2:

Duyệt mảng total để tìm đội có điểm cao nhất.

Trong C++, vì total là một vector nên để lấy ra phần tử lớn nhất, ta có thể dùng hàm max_element().

Trong khi với Python, ta tự viết vòng lặp và hàm enumerate() để duyệt total.

C++Python

    // biến it trỏ vào phần tử lớn nhất trong vector total
    vector<lli>::iterator it = max_element(total.begin(), total.end());

    // Lấy giá trị của phần tử lớn nhất đó
    max_score = *it;

    // Lấy chỉ số (vị trí) của phần tử lớn nhất đó
    max_team = distance(total.begin(), it) + 1;

    # Duyệt từng điểm tổng trong mảng total
    for i, score in enumerate(total):   
        if score > max_score:        
            # Cập nhật tổng điểm cao nhất
            max_score = score

            # Ghi nhận mã số của đội có điểm cao nhất
            max_team = i + 1

Mã nguồn¶

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

Bài 3: Số nguyên tố¶

Đề bài¶

Số nguyên tố là số nguyên dương chỉ có duy nhất hai ước là 1 và chính nó.

Yêu cầu: Cho số nguyên \(N (1 \le N \le 10^6)\) và \(N\) đoạn số nguyên \([L_i, R_i]\) \((1 \le L_i < R_i \le 10^7; 1 \le i \le N)\). Hãy tìm số lượng số nguyên tố thuộc mỗi đoạn \([L_i, R_i]\).

Dữ liệu vào: snt.inp

Dòng đầu tiên chứa số nguyên \(N\).

\(N\) dòng tiếp theo: dòng thứ i chứa hai số nguyên \(L_i, R_i\).

Dữ liệu ra: snt.out

Gồm N dòng, dòng thứ \(i\) ghi một số nguyên là số lượng số nguyên tố thuộc đoạn \([L_i, R_i]\).

Ví dụ:

snt.inp	snt.out
2 14 16 11 25	0 5

Giải thích:

Đoạn [14, 16]: không có số nguyên tố.
Đoạn [11, 25]: có 5 số nguyên tố là 11, 13, 17, 19 và 23.

Ràng buộc:

Có 40% số test tương ứng 40% số điểm của bài với \(1 \le N \le 10^3; 1 \le L_i < R_i \le 10^3\).
Có 60% số test tương ứng 60% số điểm của bài với \(1 \le N \le 10^6; 1 \le L_i < R_i \le 10^7\).

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

Ý tưởng chính¶

Vì giới hạn của r (right) là \(10^7\) nên ta có thể sử dụng sàng Eratosthenes để đánh dấu các số nguyên tố từ \(1\) đến \(10^7\).

Để đếm số lượng số nguyên tố trong đoạn [l..r], ta dùng kỹ thuật prefix sum (tổng tiền tố hoặc tổng cộng dồn).

Cụ thể, dùng hàm prime_count để lưu số lượng số nguyên tố, với prime_count[i] là số lượng số nguyên tố trong đoạn [1, i].

Như vậy, ta chỉ cần cập nhật mảng prime_count một lần là có thể áp dụng cho mọi truy vấn [l, r] của input.

Viết chương trình¶

Bước 0:

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

C++Python

const int MAX = 1E7;

int n, l, r;

// Khởi tạo sàng Eratosthenes với toàn bộ phần tử đều là 1 (true)
vector<char> E(MAX + 1, 1);

// prime_count[i] lưu số lượng số nguyên tố từ 1 đến i
vector<int> prime_count(MAX + 1, 0);

MAX = 10000000

n = l = r = 0

# Khởi tạo sàng với toàn bộ phần tử đều là 1 (true)
E = [1] * (MAX + 1)

# prime_count[i] lưu số lượng số nguyên tố từ 1 đến i
prime_count = [0] * (MAX + 1)

Bước 1:

Viết hàm để thực hiện sàng Eratosthenes.

C++Python

void sieve()
{
    // 0 và 1 không phải số nguyên tố
    E[0] = 0;
    E[1] = 0;

    // Duyệt từng số p trong phạm vi [2..sqrt(MAX)]
    for (int p = 2; p * p < MAX + 1; ++p)
    {
        // Nếu p là số nguyên tố
        if (E[p] == 1)
        {
            // thì đánh dấu 0 cho các bội của p, bắt đầu từ p * p
            for (int i = p * p; i < MAX + 1; i += p)
            {
                E[i] = 0;
            }
        }
    }
}

def sieve():
    global MAX, E

    # 0 và 1 không phải số nguyên tố
    E[0] = 0
    E[1] = 0

    # Duyệt từng số p trong phạm vi [2..sqrt(MAX)]
    for p in range(2, int(math.sqrt(MAX)) + 1):
        # Nếu p là số nguyên tố:
        if E[p] == 1:
            # thì đánh dấu 0 cho các bội của p, bắt đầu từ p * p
            for i in range(p * p, MAX + 1, p):
                E[i] = 0

Bước 2:

Viết hàm tính tổng cộng dồn (prefix sum), lưu trong mảng prime_count.

C++Python

void prefix_sum()
{
    for (int i = 1; i < MAX + 1; ++i)
    {
        prime_count[i] = prime_count[i - 1] + E[i];
    }
}

def prefix_sum():
    global E, prime_count

    for i in range(1, MAX + 1):
        prime_count[i] = prime_count[i - 1] + E[i]

Bước 3:

Vừa đọc truy vấn l và r, vừa xuất kết quả dựa vào mảng prime_count.

C++Python

    cin >> n;

    // Vừa đọc input vừa xuất kết quả
    int result;
    for (int q = 0; q < n; ++q)
    {
        cin >> l >> r;        

        // Dựa vào prefix sum, in ra số lượng số nguyên tố trong phạm vi [l, r]
        int result = prime_count[r] - prime_count[l - 1];
        cout << result << '\n';
    }

    with open(input_file, 'r') as fi, open(output_file, 'w') as fo:
        n = int(fi.readline())

        # Vừa đọc input vừa xuất kết quả
        for q in range(n):
            l, r = map(int, fi.readline().split())

            # Dựa vào prefix sum, in ra số lượng số nguyên tố trong phạm vi [l, r]
            result = prime_count[r] - prime_count[l - 1]
            fo.write(str(result) + '\n')

Mã nguồn¶

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

Bao tôi ly cafe 🧋 nhé!