Học sinh giỏi 9 Hải Dương 2023 - 2024¶

Bài 1: Tam giác cân¶

Đề bài¶

Bạn Nam có hai thanh gỗ với chiều dài lần lượt là \(a\) và \(b (a \neq b)\). Nam muốn tìm thêm một thanh gỗ nữa với chiều dài là \(c\) để dựng thành một tam giác cân với độ dài ba cạnh lần lượt là \(a, b, c\).

Yêu cầu: Hãy xác định giá trị \(c\) để diện tích tam giác tạo được là lớn nhất.

Dữ liệu: tamgiaccan.inp

Hai số nguyên dương lần lượt là \(a, b (a, b \le 1000)\) và \(a \neq b\).

Kết quả: tamgiaccan.out

Số nguyên dương c.

Ví dụ:

tamgiaccan.inp	tamgiaccan.out
10 5	10

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

Ý tưởng chính¶

Cách 1:

Viết hàm tính diện tích tam giác bằng công thức Heron: \(S = \sqrt{p(p-a)(p-b)(p-c)}\).
Gọi hàm trên hai lần, ứng với hai trường hợp: chọn \(c = a\) hoặc chọn \(c = b\).
So sánh hai diện tích với nhau và chọn \(c\) thoả yêu cầu.

Cách 2:

Để giúp viết mã lệnh tốt hơn, ta có thể phân tích bài toán như sau:

Trường hợp 1: ba cạnh của tam giác là \((a, a, b)\)

\(S_1 = \sqrt{p_1(p_1-a)(p_1-a)(p_1-b)} =\frac{b}{4}\sqrt{4a^2-b^2}\).
Trường hợp 2: ba cạnh của tam giác là \((a, b, b)\)

\(S_2 = \sqrt{p_2(p_2-a)(p_2-b)(p_2-b)} =\frac{a}{4}\sqrt{4b^2-a^2}\).

Để so sánh \(S_1\) và \(S_2\), ta thực hiện bình phương và quy đồng mẫu số.

Điều này dẫn đến việc so sánh \(4a^2b^2 - b^4\) và \(4a^2b^2 - a^4\).

Như vậy, ta cần so sánh \(a^4\) và \(b^4\).

Vì \(a, b > 0\) nên điều trên tương đương việc so sánh \(a\) và \(b\).

Nếu \(a > b\):

\(a > b \Rightarrow -a^4 < -b^4 \Rightarrow S_2 < S_1\).

Mà \(S_1\) là diện tích của tam giác \((a, a, b)\). Tức ta chọn \(c = a\).
Nếu \(a < b\):

\(a < b \Rightarrow -a^4 > -b^4 \Rightarrow S_1 < S_2\).

Mà \(S_2\) là diện tích của tam giác \((a, b, b)\). Tức ta chọn \(c = b\).

Trong cả hai trường hợp, ta đều chọn \(c\) là cạnh lớn, tức \(c = max(a, b)\).

Viết chương trình¶

C++Python

    c = max(a, b);

    c = max(a, b)

Mã nguồn¶

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

Bài 2: Tổng các chữ số¶

Đề bài¶

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

Yêu cầu: Hãy tính tổng các chữ số của \(n\) biểu diễn trong hệ thập phân.

Dữ liệu: tongchuso.inp

Số nguyên dương \(n (n \le 10^9)\).

Kết quả: tongchuso.out

Một số nguyên là tổng các chữ số của \(n\) viết trong hệ thập phân.

Ví dụ:

tongchuso.inp	tongchuso.out
193	13

Ràng buộc:

60% số test ứng với 60% số điểm của bài có \(n \le 10000\).
40% số test còn lại có \(10000 < n \le 10^9\).

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

Ý tưởng chính¶

Trích ra từng chữ số bên phải của n bằng cách lặp thao tác chia cho 10 cho đến khi không còn chia được nữa.

Viết chương trình¶

C++Python

    while (n > 0)
    {
        Sum += n % 10;
        n /= 10;
    }

    while n > 0:
        Sum += n % 10
        n = n // 10

Mã nguồn¶

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

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

Đề bài¶

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

Yêu cầu: Hãy tìm số nguyên tố nhỏ nhất lớn hơn hoặc bằng \(n\).

Dữ liệu: snt.inp

Số nguyên dương \(n (n \le 10^9)\).

Kết quả:

Một số nguyên dương là số nguyên tố nhỏ nhất lớn hơn hoặc bằng \(n\).

Ví dụ:

snt.inp	snt.out
20	23

Ràng buộc:

60% số test ứng với 60% số điểm của bài có \(n \le 1000\).
40% số test còn lại có \(1000 < n \le 10^9\).

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

Ý tưởng chính¶

Viết hàm kiểm tra số nguyên tố.

Duyệt từng giá trị n, n + 1, n + 2, ... cho đến khi tìm được số nguyên tố.

Viết chương trình¶

Bước 1:

Viết hàm kiểm tra số nguyên tố.

C++Python

bool is_prime(int x)
{
    if (x < 1) return false;

    if (x < 4) return true;

    if (x % 2 == 0) return false;

    if (x % 3 == 0) return false;

    for (int i = 5; i * i < x + 1; i += 6)
    {
        if (x % i == 0) return false;
        if (x % (i + 2) == 0) return false;
    }

    return true;
}

def is_prime(x):
    if x < 1:
        return False

    if x < 4:
        return True

    if x % 2 == 0 or x % 3 == 0:
        return False

    for i in range(5, int(math.sqrt(x)) + 1, 6):
        if x % i == 0 or x % (i + 2) == 0:
            return False

    return True

Bước 2:

Dùng vòng lặp while, duyệt tìm số nguyên tố gần n nhất.

C++Python

    while (true)
    {
        if (is_prime(n))
        {
            result = n;
            break;
        }

        n++;
    }

    while True:
        if is_prime(n):
            result = n
            break

        n += 1

Mã nguồn¶

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

Bài 4: Bánh trung thu¶

Đề bài¶

Lớp 9A có \(m\) học sinh, thật tình cờ \(m\) lại là số nguyên tố lẻ.

Nhân dịp tết Trung thu, cô chủ nhiệm quyết định mua một hộp bánh lớn về liên hoan. Các cửa hàng bánh đều bố trí hộp bánh trung thu có dạng một tam giác cân với tầng dưới cùng xếp n gói bánh. Số gói bánh của tầng trên luôn nhỏ hơn số gói bánh của tầng dưới 1 gói. Tầng trên cùng có 1 gói bánh. Ví dụ: hộp bánh trung thu với \(n = 5\) có dạng:

    ⏹️  
   ⏹️⏹️  
  ⏹️⏹️⏹️  
 ⏹️⏹️⏹️⏹️  
⏹️⏹️⏹️⏹️⏹️

Số lượng gói bánh trong hộp bánh trên là 15.

Yêu cầu: Quỹ lớp chỉ còn lại số tiền đủ để mua một hộp bánh có kích thước tầng dưới tối đa là \(n\). Hãy giúp cô chủ nhiệm tính xem có bao nhiêu loại hộp bánh có thể mua mà số gói bánh trong hộp chia đều được cho \(m\) học sinh.

Dữ liệu: banhtrungthu.inp

Hai số nguyên dương \(m, n (m \le 1000, n \le 10^6)\).

Kết quả: banhtrungthu.out

Số loại hộp bánh có kích thước tầng dưới không quá \(n\) mà số gói bánh trong hộp chia đều cho \(m\) học sinh.

Ví dụ:

banhtrungthu.inp	banhtrungthu.out
7 20	5

Giải thích:

Các loại hộp bánh phù hợp là: 6, 7, 13, 14 và 20.

Số gói bánh trong mỗi loại hộp đều chia hết cho 7.

Như vậy, có tất cả 5 loại hộp thoả yêu cầu.

Ràng buộc:

60% số test ứng với 60% số điểm của bài có \(n \le 1000\).
20% số test tiếp theo ứng với 20% số điểm của bài có \(1000 < n \le 10^6\).
20% số test còn lại ứng với 20% số điểm của bài có \(10^6 < n \le 10^9\).

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

Ý tưởng chính¶

Xét hộp bánh loại \(k\).

Theo đề bài, số gói bánh trong hộp loại \(k\) là:

\(S = 1 + 2 + 3 + ... + k = \frac{k(k + 1)}{2}\).

Ta có:

\(k(k + 1)\) phải chia hết cho \(2m\). (Vì số gói bánh phải chia hết cho số học sinh \(m\), hay \(\frac{k(k + 1)}{2}\) phải chia hết cho \(m\))
\(k(k + 1)\) luôn chia hết cho \(2\). (vì một trong hai số \(k\) và \(k + 1\) là chẵn)
2 và \(m\) là nguyên tố cùng nhau. (vì \(m\) là số lẻ)

Do đó, \(k(k + 1)\) phải chia hết cho \(m\).

Mà \(m\) là số nguyên tố.

Suy ra, \(k\) chia hết cho \(m\) hoặc \(k + 1\) chia hết cho \(m\).

Xét trường hợp \(k\) chia hết cho \(m\). Điều này có nghĩa \(q = \frac{k}{m}\) với \(q\) là số nguyên dương.

Các giá trị hợp lệ của \(q\) gồm: \(1, 2, 3, ..., \frac{n}{m}\).

Như vậy, số lượng các giá trị \(k\) có thể chọn là \(\frac{n}{m}\). \((1)\)

Lập luận tương tự, với trường hợp \(k + 1\) chia hết cho \(m\), số lượng các giá trị \(k + 1\) có thể chọn là \(\frac{n + 1}{m}\). \((2)\)

Mà một giá trị \(k\) không thể vừa chia hết cho \(m\) vừa chia cho \(m\) dư \(m - 1\).

Vậy tổng số lượng giá trị \(k\) cần tìm là tổng của \((1)\) và \((2)\), tức \(\frac{n}{m} + \frac{n + 1}{m}\).

Viết chương trình¶

Mã nguồn¶

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

Bài 5: Giải phương trình¶

Đề bài¶

Ký hiệu \(s(x)\) là hàm tính tổng các chữ số của \(x\) viết trong hệ thập phân. Ví dụ: \(s(15) = 6, s(2024) = 8\).

Yêu cầu: Viết chương trình tìm số nghiệm nguyên dương của phương trình \(x + s(x) = n\). Trong đó, \(n\) là số nguyên dương cho trước, \(x\) là ẩn số.

Dữ liệu: phuongtrinh.inp

Số nguyên dương \(n (n \le 10^9)\).

Kết quả: phuongtrinh.out

Một số nguyên không âm là số nghiệm nguyên dương của phương trình trên.

Ví dụ:

phuongtrinh.inp	phuongtrinh.out	Giải thích
216	2	\(x + s(x) = 216\) có 2 nghiệm là 198 và 207.

Ràng buộc:

60% số test ứng với 60% số điểm của bài có \(n \le 1000\).
40% số test còn lại ứng với 40% số điểm của bài có \(1000 < n \le 10^9\).

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

Ý tưởng chính¶

Ta có: \(x + s(x) = n \Rightarrow x = n - s(x)\)

Vì \(s(x)\) là tổng các chữ số của \(x\) nên \(s(x)\) dương.

Suy ra \(x < n \le 10^9\)

Như vậy, giá trị lớn nhất của \(x\) có thể là \(999,999,999\), tức \(s(x) \le 81\).

\(\Rightarrow -s(x) \ge -81\)

\(\Rightarrow x = n - s(x) = n + (-s(x)) \ge n + (-81) = n - 81\)

Vậy ta sẽ dùng vòng lặp cho x chạy từ n - 81 đến n, kiểm tra xem giá trị nào của x là nghiệm thì cập nhật biến đếm count_x.

Ngoài ra, để tránh việc n - 81 ra giá trị âm, ta có thể lấy giá trị xuất phát của x bằng max(1, n - 81).

Viết chương trình¶

Bước 1:

Viết hàm \(s(x)\) tính tổng các chữ số.

C++Python

int sum_digits(int a)
{
    int Sum = 0;
    while (a > 0)
    {
        Sum += a % 10;
        a /= 10;
    }

    return Sum;
}

def sum_digits(a):
    Sum = 0
    while a > 0:
        Sum += a % 10
        a = a // 10

    return Sum

Bước 2:

Dùng vòng lặp kiểm tra x thoả điều kiện và đếm số lượng giá trị x thoả phương trình.

C++Python

    // Khởi tạo giá trị xuất phát của nghiệm x
    int start_x = max(1, n - 81);

    // Duyệt từng giá trị x từ start_x đến n
    for (int x = start_x; x < n; ++x)
    {
        if (x + sum_digits(x) == n)
        {
            count_x++;
        }
    }

    # Khởi tạo giá trị xuất phát của nghiệm x
    start_x = max(1, n - 81)

    # Duyệt từng giá trị x từ start_x đến n 
    for x in range(start_x, n):
        if x + sum_digits(x) == n:
            count_x += 1

Mã nguồn¶

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

Bao tôi ly cafe 🧋 nhé!