Học sinh giỏi 9 Thanh Hoá 2023 - 2024¶

Bài 1: Chuẩn hoá xâu¶

Đề bài¶

Lam muốn đặt tên các biến trong mã nguồn chương trình của mình theo chuẩn PropCase. Chuẩn PropCase quy ước như sau:

Tên biến gồm các chữ cái Latinh 'A'..'Z', 'a'..'z' và chữ số '0'..'9';
Chữ cái đầu tiên của tên biến không bắt đầu bằng chữ số '0'..'9';
Chữ cái đầu tiên của mỗi từ tiếp theo trong tên biến được viết in hoa;
Ví dụ: DiemTbHK1, lop9A10, v.v...

Lam muốn tải mã nguồn của mình lên Github với các biến được đặt tên theo chuẩn join_case có quy ước:

Tên biến gồm các chữ cái Latinh 'a'..'z', chữ số '0'..'9' và dấu gạch nối '_';
Không bắt đầu bằng chữ số '0'..'9' hoặc dấu gạch nối '_';
Hai từ trong tên biến được tách nhau bởi dấu '_';
Ví dụ: diem_tb_hk1, lop9_a10, ...

Yêu cầu: Hãy giúp Lam đổi tên biến từ chuẩn PropCase sang chuẩn join_case.

Dữ liệu: CHUANHOAXAU.INP

Một xâu độ dài \(n (1 \le n \le 1000)\) là một tên biến đặt theo chuẩn PropCase.

Kết quả: CHUANHOAXAU.OUT

Một xâu là tên biến đặt lại theo chuẩn join_case.

Ví dụ:

CHUANHOAXAU.INP	CHUANHOAXAU.OUT
DiemTbHK1	diem_tb_hk1
lop9A10	lop9_a10

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

Ý tưởng chính¶

Duyệt từng ký tự của chuỗi ban đầu và ghép vào chuỗi mới. Nếu gặp ký tự in hoa thì biến đổi thành ký tự thường và thêm ký tự '_' vào trước nó.

Viết chương trình¶

C++Python

    char current;

    // Duyệt từng ký tự trong chuỗi ban đầu
    for (int i = 0; i < prop_string.length(); ++i)
    {
        // ký tự đang xét
        current = prop_string[i];

        // Nếu ký tự đang xét là in hoa
        if (isupper(prop_string[i]))
        {
            // Nếu không phải ký tự in hoa đầu tiên thì thêm gạch
            if (i > 0) join_string += '_';

            // Chuyển ký tự in hoa thành thường
            join_string += tolower(current);
        }
        else
        {
            join_string += current;
        }
    }

    # Duyệt từng ký tự trong chuỗi ban đầu
    for i in range(len(prop_string)):
        # ký tự đang xét
        current = prop_string[i]

        # Nếu ký tự đang xét là in hoa
        if current.isupper():
            # Nếu không phải ký tự in hoa đầu tiên thì thêm gạch
            if i > 0:
                join_string += '_'

            # Chuyển ký tự in hoa thành thường
            join_string += current.lower()
        else:
            join_string += current

Mã nguồn¶

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

Bài 2: Gà và chó¶

Đề bài¶

Yêu cầu: Đếm số cách mua một con gà và một con chó sao cho tổng số tiền phải trả để mua cả hai con không vượt quá \(n (3 \le n \le 2 \times 10^9)\). Biết số tiền mua gà luôn ít hơn số tiền mua chó. Số tiền mua gà và mua chó là các số nguyên dương.

Dữ liệu: GACHO.INP

Số nguyên dương \(n\).

Kết quả: GACHO.OUT

Số nguyên là đáp số của bài toán.

Ví dụ:

GACHO.INP	GACHO.OUT	Giải thích
5	4	Có 4 cách mua cặp (gà, chó) với tổng số tiền không quá 5 là: (1,2); (1,3); (1,4); (2,3).

Ràng buộc:

Có 70% số test ứng với 70% số điểm của bài có \(n \le 10^3\).
Có 20% số test ứng với 20% số điểm của bài có \(n \le 10^6\).
Có 10% số test ứng với 10% số điểm của bài có \(n \le 2 \times 10^9\).

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

Ý tưởng chính¶

Đặt \(g, c\) là lần lượt là số tiền mua gà và mua chó.

Ta có:

\(g < c\) và \(g + c \le n\)

Suy ra \(g + 1 \le c \le n - g\)

Suy ra \(g \le \frac{n - 1}{2}\)

Đặt \(k = \left\lfloor \frac{n - 1}{2}\right\rfloor\).

\(g\) có thể nhận các giá trị nguyên từ 1 đến \(k\).

Ứng với mỗi giá trị \(g\), giá trị \(c\) có thể là: \(g + 1, g + 2, ..., n - g\).

Suy ra, ứng với mỗi giá trị \(g\), số lượng giá trị \(c\) hay số cách chọn \(c\) là: \((n - g) - (g + 1) + 1 = n - 2g\).

Tổng số cách mua là tổng số giá trị \(c\) khả thi ứng với từng g.

Nói cách khác, tổng số cách mua \(S\) là:

\[\begin{aligned} S &= \sum_{g=1}^{k}(n - 2g) \\ &= \sum_{g=1}^{k}n - \sum_{g=1}^{k}2g \\ &= n.k - 2\sum_{g=1}^{k}g \\ &= n.k - 2.\frac{k(k+1)}{2} \\ &= k.(n - k - 1) \end{aligned}\]

Viết chương trình¶

C++Python

    lli k = (n - 1) / 2;

    result = k * (n - k - 1);

    k = (n - 1) // 2

    result = k * (n - k - 1)

Mã nguồn¶

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

Bài 3: Số đặc biệt¶

Đề bài¶

Một số tự nhiên được gọi là số đối xứng nếu viết các chữ số của nó theo chiều ngược lại thì vẫn thu được chính nó. Ví dụ: các số 88, 858 là những số đối xứng.

Một số được coi là số đặc biệt nếu nó là số đối xứng và có từ 3 ước số nguyên tố khác nhau trở lên. Ví dụ: 858 là số đặc biệt vì nó là số đối xứng và có 4 ước nguyên tố khác nhau là 2, 3, 11, 13; còn số 88 không là số đặc biệt vì nó đối xứng nhưng chỉ có 2 ước nguyên tố khác nhau là 2, 11.

Yêu cầu: Cho 2 số nguyên dương \(a, b\). Tính tổng các số đặc biệt trong đoạn từ \(a\) đến \(b\).

Dữ liệu: SODACBIET.INP

Hai số nguyên dương \(a, b (1 \le a < b \le 10^7)\).

Kết quả: SODACBIET.OUT

Một số duy nhất là tổng tìm được.

Ví dụ:

SODACBIET.INP	SODACBIET.OUT
88 858	11605

Ràng buộc:

Có 60% số test ứng với 60% số điểm của bài có \(1 \le a < b \le 10^3\).
Có 20% số test ứng với 20% số điểm của bài có \(10^3 \le a < b \le 10^6\).
Có 20% số test ứng với 20% số điểm của bài có \(10^6 \le a < b \le 10^7\).

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

Ý tưởng chính¶

Duyệt từng số trong đoạn [a..b]:

Kiểm tra mỗi số có phải là đối xứng không.
Nếu là đối xứng thì tính số lượng ước số mà là nguyên tố của nó, rồi cộng dồn vào tổng chung.

Viết chương trình¶

Bước 1:

Viết hàm kiểm tra một số n có đối xứng hay không.

C++Python

bool is_palindrome(int n)
{
    // Số có một chữ số thì luôn đối xứng
    if (n <10) return true;

    // Số có hàng đơn vị là 0 thì không đối xứng
    if (n % 10 == 0) return false;

    // biến lưu số ban đầu và số đảo ngược
    int original = n;
    int reversed = 0;

    int digit;
    while (n > 0)
    {
        // Lấy ra chữ số hàng đơn vị
        digit = n % 10;

        // Ghép vào đầu của số đảo ngược
        reversed = reversed * 10 + digit;

        n /= 10;
    }

    return original == reversed;
}

def is_palindrome(n):
    # Số có một chữ số thì luôn đối xứng
    if n < 10:
        return True

    # Số có hàng đơn vị là 0 thì không đối xứng
    if n % 10 == 0:
        return False

    # biến lưu số ban đầu và số đảo ngược
    original = n
    reversed = 0

    while n > 0:
        # Lấy ra chữ số hàng đơn vị
        digit = n % 10

        # Ghép vào đầu của số đảo ngược
        reversed = reversed * 10 + digit

        n //= 10

    return original == reversed

Bước 2:

Viết hàm tính số lượng ước số mà là nguyên tố của một số number.

Hàm này thực hiện như sau:

Lần lượt chia số number cho 2, 3, 5, v.v... và các số lẻ tiếp theo. Nếu chia hết thì các số lẻ (kể cả 2) chắc chắn là ước nguyên tố.
Khi đã tìm thấy ước nào đó, thì vẫn dùng vòng lặp chia tiếp cho ước đó nhằm loại bỏ nó.
Lưu trữ các ước tìm thấy bằng set (trong cả C++ lẫn Python) nhằm bảo đảm mỗi ước chỉ lưu một lần.

Hàm này thực hiện công việc hoàn toàn tương tự phân tích một số nguyên thành tích của các thừa số nguyên tố, chỉ khác là không quan tâm số mũ.

C++Python

int count_prime(int number)
{
    if (number == 1) return 0;

    // biến lưu các thừa số nguyên tố khác nhau
    set<int> factors;

    int n = number;

    // Kiểm tra 2 có phải là ước không
    if (n % 2 == 0)
    {
        factors.insert(2);

        while (n % 2 == 0)
        {
            n /= 2;
        }
    }

    // Kiểm tra các ước số lẻ từ 3 trở đi
    for (int i = 3; i * i < n + 1; i += 2)
    {
        if (n % i == 0)
        {
            factors.insert(i);

            while (n % i == 0)
            {
                n /= i;
            }
        }
    }

    // Sau khi chia, nếu n vẫn lớn hơn 2 thì n là một ước nguyên tố
    if (n > 2)
    {
        factors.insert(n);
    }

    return factors.size();
}

def count_prime(number):
    if number == 1:
        return 0

    # biến lưu các thừa số nguyên tố khác nhau
    factors = set()

    n = number

    # Kiểm tra 2 có phải là ước không
    if n % 2 == 0:
        factors.add(2)

        while n % 2 == 0:
            n //= 2

    # Kiểm tra các ước số lẻ từ 3 trở đi
    for i in range(3, int(math.sqrt(n)) + 1):
        if n % i == 0:
            factors.add(i)

            while n % i == 0:
                n //= i

    # Sau khi chia, nếu n vẫn lớn hơn 2 thì n là một ước nguyên tố
    if n > 2:
        factors.add(n)

    return len(factors)

Bước 3:

Gọi hai hàm trên ra thực hiện và cộng dồn kết quả vào tổng chung.

C++Python

    // Duyệt từng số từ a đến b
    for (int i = a; i < b + 1; ++i)
    {
        if (is_palindrome(i))
            if (count_prime(i) >= 3)
                number_of_special_numbers += i;
    }

    # Duyệt từng số từ a đến b
    for i in range(a, b + 1):
        if is_palindrome(i):
            if count_prime(i) >= 3:
                number_of_special_numbers += i

Mã nguồn¶

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

Bài 4: Đường thẳng¶

Đề bài¶

Trên cùng một mặt phẳng toạ độ cho \(n\) đường thẳng phân biệt đánh số từ 1 tới \(n\). Đường thẳng \(i\) có dạng \(y = a_ix + b_i (1 \le i \le n)\).

Yêu cầu: đếm số cặp đường thẳng song song trong \(n\) đường thẳng trên.

Dữ liệu: DUONGTHANG.INP

Dòng đầu tiên là số nguyên \(n (2 \le n \le 3 \times 10^6)\).
\(n\) dòng sau, mỗi dòng ghi 2 số nguyên \(a_i, b_i\) biểu diễn đường thẳng thứ \(i (|a_i|, |b_i| \le 10^9; 1 \le i \le n)\).

Kết quả: DUONGTHANG.OUT

Một số nguyên là đáp số của bài.

Ví dụ:

DUONGTHANG.INP	DUONGTHANG.OUT
3 1 2 1 -2 0 2	1
3 1 2 1 -2 1 -4	3

Ràng buộc:

Có 50% số test ứng với 50% số điểm của bài có \(2 \le n \le 10^3; |a_i|, |b_i| \le 10^5\).
Có 25% số test ứng với 25% số điểm của bài có \(10^3 < n \le 10^5; |a_i|, |b_i| \le 10^5\).
Có 25% số test ứng với 25% số điểm của bài có \(10^3 < n \le 3 \times 10^6; |a_i|, |b_i| \le 10^9\).

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

Ý tưởng chính¶

Do hai đường thằng song song thì có cùng hệ số góc, nên ta chỉ cần đếm số lượng hệ số góc giống nhau thì sẽ biết được số đường thẳng song song nhau, từ đó tính được số cặp song song.

Để đếm số lượng hệ số góc giống nhau, ta chỉ cần sắp xếp các hệ số góc theo thứ tự tăng dần, rồi dùng một vòng lặp là đếm được.

Gọi \(k\) là số lượng hệ số góc giống nhau.

Số cặp đường thẳng song song là:

\[\begin{aligned} \mathrm{C}_{k}^{2} &= \frac{k!}{2!(k - 2)!} \\ &= \frac{(k-2)!(k - 1)k}{2!(k - 2)!} \\ &= \frac{k(k - 1)}{2} \end{aligned}\]

Viết chương trình¶

C++Python

    // Sắp xếp lại các hệ số góc a theo thứ tự tăng dần
    sort(A.begin(), A.end());

    // biến tạm dùng để lưu số lượng đường thẳng có cùng hệ số góc a
    lli tmp_count = 1;

    // Duyệt từng hệ số góc từ vị trí 1 trở đi
    for (int i = 1; i < n; ++i)
    {
        // Nếu hệ số góc vẫn như cũ
        if (A[i] == A[i - 1])
            // thì tăng số đường thẳng có cùng hệ số góc thêm 1
            tmp_count++;
        else
        {
            // Nếu có nhiều hơn 1 đường thẳng có cùng hệ số góc a
            if (tmp_count > 1)
                // thì tính số cặp song song
                parallel += tmp_count * (tmp_count - 1) / 2;

            // khởi tạo lại tmp_count để đếm lại cho hệ số góc mới
            tmp_count = 1;
        }
    }

    // Tính cho nhóm hệ số góc cuối cùng
    if (tmp_count > 1)
        parallel += tmp_count * (tmp_count - 1) / 2;

    # Sắp xếp lại các hệ số góc a theo thứ tự tăng dần
    A.sort()

    # biến tạm dùng để lưu số lượng đường thẳng có cùng hệ số góc a
    tmp_count = 1

    # Duyệt từng hệ số góc từ vị trí 1 trở đi
    for i in range(1, n):
        # Nếu hệ số góc vẫn như cũ
        if A[i] == A[i - 1]:
            # thì tăng số đường thẳng có cùng hệ số góc thêm 1
            tmp_count += 1
        else:
            # Nếu có nhiều hơn 1 đường thẳng có cùng hệ số góc a
            if tmp_count > 1:
                # thì tính số cặp song song
                parallel += tmp_count * (tmp_count - 1) // 2

                # khởi tạo lại tmp_count để đếm lại cho hệ số góc mới
                tmp_count = 1

    #  Tính cho nhóm hệ số góc cuối cùng
    if tmp_count > 1:
        parallel += tmp_count * (tmp_count - 1) // 2

Mã nguồn¶

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

Bao tôi ly cafe 🧋 nhé!