Tuyển sinh 10 Hà Tĩnh 2023 - 2024¶

Bài 1: Tổng dãy số¶

Đề bài¶

Cho dãy số \(T_1, T_2, T_3, ..., T_n\).

Với số hạng tổng quát là: \(T_k = (k+1)^2 - k^2\) (\(k\) là số nguyên và \(1 \le k \le n\)).

Yêu cầu: Tính giá trị \(S = T_1, T_2, T_3, ..., T_n\)

Dữ liệu: Vào từ file văn bản SUMS.INP gồm một dòng duy nhất chứa số nguyên dương \(n (1 \le n \le 10^9)\).

Kết quả: Ghi ra file văn bản SUMS.OUT một số nguyên là giá trị S tính được.

Ví dụ:

SUMS.INP	SUMS.OUT	Giải thích
2	8	Với n = 2 ta có: \(S = T_1 + T_2 = (1 + 1)^2 – 1^2 + (2 + 1)^2 - 2^2 = 8\)

Ràng buộc:

Có 70% số test ứng với 70% số điểm thỏa mãn \(1 \le n \le 10^6\).
Có 30% số test còn lại ứng với 30% số điểm không có ràng buộc gì thêm.

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

Ý tưởng chính:¶

Dựa vào biểu thức \(T_k = 2k + 1\), ta có:

\[ \begin{aligned} S &= (2 \cdot 1 + 1) + (2 \cdot 2 + 1) + ... + (2 \cdot n + 1)\\ &= (2 \cdot 1 + 2 \cdot 2 + ... + 2 \cdot n) + (1 + 1 + ... + 1) \end{aligned} \]

Tách tổng này thành hai phần:

\[ 2(1 + 2 + 3 + ... + n) = 2 \cdot \frac{n(n+1)}{2} = n(n+1) \]

và

\[ 1 + 1 + ... + 1 = n \]

Do đó,

\[ S = n(n+1) + n = n(n+2) \]

Như vậy, bài này chỉ cần giải quyết bằng một dòng lệnh.

Vì giới hạn của \(n\) là \(10^9\) nên trong C++, ta khai báo kiểu long long int cho biến n và S.

Viết chương trình¶

C++Python

    S = n * (n + 2);

    S = n * (n + 2)

Mã nguồn¶

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

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

Đề bài¶

Nam phát hiện nhiều số tự nhiên có tính chất: Tổng bình phương các chữ số của nó là số nguyên tố, những số như thế Nam gọi là số đặc biệt.

Yêu cầu: Cho số nguyên dương n. Hãy kiểm tra xem n có phải là số đặc biệt hay không.

Dữ liệu: Vào từ file văn bản BNUM.INP gồm một dòng duy nhất chứa số nguyên dương \(n (10 \le n \le 10^18)\).

Kết quả: Ghi ra file văn bản BNUM.OUT gồm 2 dòng:

Dòng đầu ghi ra 1 nếu n là số đặc biệt, ngược lại ghi -1 nếu n không phải là số đặc biệt.
Dòng thứ hai ghi tổng bình phương các chữ số của n.

Ví dụ:

BNUM.INP	BNUM.OUT	Giải thích
21	1 5	Tổng bình phương chữ số của 21 là 5 (5 là số nguyên tố)
24	-1 20	Tổng bình phương chữ số của 24 là 20 (20 không phải số nguyên tố)

Ràng buộc:

Có 60% số test ứng với 60% số điểm thỏa mãn: \(10 \le n \le 10^3\).
40% số test còn lại ứng với 40% số điểm không có ràng buộc gì thêm.

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

Ý tưởng chính¶

Đọc n dưới dạng chuỗi string.

Duyệt từng ký tự của n, tính bình phương và cộng dồn vào tổng. Sau đó kiểm tra xem tổng có phải là nguyên tố hay không.

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 n)
{
    if (n < 2) return false;
    if (n < 4) return true;
    if (n % 2 == 0) return false;
    if (n % 3 == 0) return false;

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

    return true;
}

def is_prime(x):
    if x < 2:
        return False
    if x < 4:
        return True
    if x % 2 == 0 :
        return False
    if x % 3 == 0:
        return False
    for i in range(5, int(x**0.5) + 1, 6):
        if n % i == 0:
            return False
        if n % (i + 2) == 0:
            return False

    return True

Bước 2:

Để có thể xử lý được từng chữ số, ta đọc giá trị của \(n\) theo kiểu string.

Kế đến, để chuyển đổi từng ký tự c trong chuỗi n thành số, ta thực hiện c - '0'. Vì trong bảng mã ASCII và UTF-8, các ký tự '0', '1', '2', ..., '9' mang các giá trị liên tiếp nhau.

Cuối cùng, gọi hàm is_prime() để kiểm tra nguyên tố.

C++Python

    sum_digit = 0;
    int digit;

    // Duyệt từng chữ số trong chuỗi n
    for (char c : n)
    {
        // Chuyển đổi chữ số thành số
        digit = c - '0';

        // Tính tổng bình phương
        sum_digit += digit * digit;
    }

    if (is_prime(sum_digit))
        prime = 1;
    else
        prime = -1;

    # Duyệt từng chữ số trong chuỗi n
    # chuyển đổi và tính tổng bình phương
    sum_digit = sum((int(c) ** 2) for c in n)

    prime = 1 if is_prime(sum_digit) else -1

Mã nguồn¶

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

Bài 3: Dãy đặc trưng¶

Đề bài¶

Cho một dãy A gồm n số nguyên \(a_1, a_2, ..., a_n\), mỗi phần tử có giá trị tuyệt đối không quá \(10^9\).

Dãy đặc trưng A1 của A là dãy con gồm các phần tử liên tiếp nhau thỏa mãn:

Trong dãy A1 tất cả các số đều dương hoặc đều âm.
Số lượng phần tử của dãy A1 là lớn nhất.

Yêu cầu: Tìm dãy A1 và ghi ra số lượng phần tử của nó.

Dữ liệu: Vào từ file văn bản SPEC.INP gồm 2 dòng:

Dòng đầu chứa số nguyên dương \(n (n \le 10^6)\).
Dòng thứ hai chứa n số a1, a2, …, an.

Kết quả: Ghi ra file văn bản SPEC.OUT số lượng phần tử của dãy A1.

Ví dụ:

SPEC.INP	SPEC.OUT	Giải thích
9 1 -3 -2 1 3 1 5 -3 -4	4	Dãy A1 là: 1 3 1 5. Dãy có 4 phần tử.
7 8 -1 -2 -3 -5 -6 4	5	Dãy A1 là: -1 -2 -3 -5 -6. Dãy có 5 phần tử.

Ràng buộc:

Có 60% số test ứng với 60% số điểm thỏa mãn: \(n \le 10^3\).
40% số test còn lại ứng với 40% số điểm không có ràng buộc gì thêm.

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

Ý tưởng chính¶

Vì mỗi phần tử của mảng input có giới hạn giá trị lên đến \(10^9\) và thao tác chủ yếu chỉ là xét âm hoặc dương nên để cải thiện hiệu suất, ta không lưu các phần tử như input, mà chỉ lưu 1 và 0, ứng với dương và âm.

Sau đó ta chỉ cần duyệt mảng chỉ có 0 và 1 này để tìm ra độ dài lớn nhất.

Viết chương trình¶

Bước 1:

Đọc input và lưu vào mảng A.

C++Python

    cin >> n;

    int x;
    for (int i = 0; i < n; ++i)
    {
        cin >> x;

        if (x > 0)
            A.push_back(1);
        else
            A.push_back(0);
    }

    with open(input_file, 'r') as f:
        n = int(f.readline().strip())
        A = list(map(lambda x: 1 if int(x) > 0 else 0, f.readline().split()))

Bước 2:

Khởi tạo bộ đếm số dương count_positive = 0 (đếm các phần tử 1) và bộ đếm số âm count_negative = 0 (đếm các phần tử 0).

Duyệt từng phần tử 0 và 1 của mảng A:

Nếu phần tử tiếp theo là âm hoặc dương thì tăng 1 cho bộ đếm tương ứng và gán 0 cho bộ đếm còn lại.
Ghi nhận độ dài âm lớn nhất và độ dài dương lớn nhất.

So sánh hai độ dài lớn nhất để ra kết quả cần tìm.

C++Python

    // Khởi tạo hai bộ đếm dương và âm
    int count_positive = 0;
    int count_negative = 0;

    // Khởi tạo độ dài lớn nhất cho dãy âm và dương
    int max_positive = 0;
    int max_negative = 0;

    // Duyệt từng phần tử của mảng A
    for (char a : A)
    {
        // Tăng 1 cho bộ đếm tương ứng với âm hoặc dương
        // và gán 0 cho bộ đếm còn lại
        if (a == 1)
        {
            count_positive += 1;
            count_negative = 0;
        }
        else
        {
            count_positive = 0;
            count_negative += 1;
        }

        // Ghi nhận hai độ dài lớn nhất
        max_positive = max(max_positive, count_positive);
        max_negative = max(max_negative, count_negative);
    }

    return max(max_positive, max_negative);

    # Khởi tạo hai bộ đếm dương và âm
    count_positive = 0
    count_negative = 0

    # Khởi tạo độ dài lớn nhất cho dãy âm và dương
    max_positive = 0
    max_negative = 0

    # Duyệt từng phần tử của mảng A
    for a in A:
        # Tăng 1 cho bộ đếm tương ứng với âm hoặc dương
        # và gán 0 cho bộ đếm còn lại
        if a == 1:
            count_positive += 1
            count_negative = 0
        else:
            count_positive = 0
            count_negative += 1

        # Ghi nhận hai độ dài lớn nhất
        max_positive = max(max_positive, count_positive)
        max_negative = max(max_negative, count_negative)

    return max(max_positive, max_negative)

Mã nguồn¶

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

Bài 4: Đoạn thẳng¶

Đề bài¶

Trên trục Ox cho n điểm, điểm thứ \(i\) ở vị trí tọa độ là \(x_i (1 \le i \le n)\). Mỗi điểm được tô một trong ba màu xanh, đỏ, vàng.

Yêu cầu: Tìm trên trục số một đoạn thẳng thỏa mãn:

Trong đoạn đó mỗi màu xuất hiện ít nhất một lần.
Độ dài đoạn thẳng là nhỏ nhất.

Dữ liệu: Vào từ file PPOINT.INP:

Dòng đầu chứa số nguyên dương \(n (1 \le n \le 10^6)\).
n dòng tiếp theo, mỗi dòng gồm hai giá trị \(x_i\) và \(m_i\):
- Số nguyên \(x_i\) là tọa độ của điểm thứ \(i\) trên trục số \((1 \le x_i \le 10^9, 1 \le i \le n)\).
- Số nguyên \(m_i\) là ký hiệu màu của các điểm, trong đó \(m_i = 1\) là màu xanh, \(m_i = 2\) là màu đỏ, \(m_i = 3\) là màu vàng.

Kết quả: Ghi ra file PPOINT.OUT một số là độ dài đoạn thẳng thỏa mãn yêu cầu, nếu không tìm thấy đoạn nào thỏa mãn thì ghi -1.

Ví dụ:

PPOINT.INP	PPOINT.OUT	Giải thích
6 2 1 4 1 5 2 7 2 8 3 10 3	4	Đoạn thẳng từ điểm có tọa độ 4 đến điểm có tọa độ 8 có độ dài là 8 – 4 = 4 gồm có 1 điểm màu xanh, 2 điểm màu đỏ và 1 điểm màu vàng.

Ràng buộc:

Có 30% số test ứng với 30% số điểm thỏa mãn: \(1 \le n \le 10^2\).
30% số test khác ứng với 30% số điểm thỏa mãn: \(n \le 10^3\).
40% số test còn lại ứng với 40% số điểm không có ràng buộc gì thêm.

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

Ý tưởng chính¶

Sắp xếp mảng P gồm các điểm theo thứ tự toạ độ tăng dần.

Duyệt mảng P, cập nhật toạ độ mới của mỗi màu, cho đến khi tìm thấy đủ cả ba màu thì tính độ dài của đoạn thẳng tương ứng (bằng cách lấy toạ độ cuối trừ toạ độ đầu). Sau đó cập nhật độ dài nhỏ nhất.

Viết chương trình¶

Bước 0:

Trong C++, tạo cấu trúc point gồm hai thành phần x và m.

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

C++Python

    struct point
    {
        int x;
        int m;
    };

    int n;
    vector<point> P;

    // độ dài nhỏ nhất cần tìm
    int min_len = INT_MAX;

    n = 0
    P = []

    # độ dài nhỏ nhất cần tìm
    min_len = sys.maxsize

Bước 1:

Trong C++, viết hàm compare() dùng làm tham số cho hàm sort().

C++

bool compare(const point& a, const point& b)
{
    return a.x < b.x;
}

Sắp xếp mảng P gồm các điểm theo thứ tự toạ độ tăng dần.

C++Python

    sort(P.begin(), P.end(), compare);

    P.sort(key=lambda point: point[0])

Bước 2:

Khởi tạo last_green = -1, last_red = -1 và last_yellow = -1. Các biến này dùng để ghi nhận toạ độ mới nhất tìm thấy các màu xanh, đỏ và vàng tương ứng.

Duyệt từng phần tử của mảng P:

Mỗi khi tìm thấy màu nào thì ghi nhận toạ độ mới của màu đó.
Nếu tìm thấy đủ cả ba toạ độ của ba màu thì tính độ dài của đoạn thẳng tương ứng (bằng cách lấy toạ độ cuối trừ toạ độ đầu), rồi cập nhật độ dài nhỏ nhất.

C++Python

    // Khởi tạo toạ độ cuối cùng tìm thấy các màu
    int last_green = -1;
    int last_red = -1;
    int last_yellow = -1;

    int min_pos;
    int max_pos;

    // Duyệt từng toạ độ trong mảng P
    for (int i = 0; i < n; ++i)
    {
        // Ghi nhận toạ độ mới khi tìm thấy màu
        if (P[i].m == 1)
            last_green = P[i].x;
        else if (P[i].m == 2)
            last_red = P[i].x;
        else if (P[i].m == 3) 
            last_yellow = P[i].x;

        // Nếu đã tìm thấy đủ ba toạ độ
        if (last_green != -1)
            if (last_red != -1)
                if (last_yellow != -1)
                {
                    // thì lấy toạ độ đầu và cuối
                    min_pos = min({last_green, last_red, last_yellow});
                    max_pos = max({last_green, last_red, last_yellow});

                    // cập nhật độ dài nhỏ nhất
                    min_len = min(min_len, max_pos - min_pos);
                }
    }

    # Khởi tạo toạ độ cuối cùng tìm thấy các màu
    last_green = -1
    last_red = -1
    last_yellow = -1

    # Duyệt mảng P
    for p in P:
        # Ghi nhận toạ độ mới khi tìm thấy màu
        if p[1] == 1:
            last_green = p[0]
        elif p[1] == 2:
            last_red = p[0]
        elif p[1] == 3:
            last_yellow = p[0]

        # Nếu đã tìm thấy đủ ba toạ độ
        # thì tính độ dài đoạn thẳng
        if last_green != -1 and last_red != -1 and last_yellow != -1:
            # thì lấy toạ độ đầu và cuối
            min_pos = min(last_green, last_red, last_yellow)
            max_pos = max(last_green, last_red, last_yellow)

            # cập nhật độ dài nhỏ nhất
            min_len = min(min_len, max_pos - min_pos)

Mã nguồn¶

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

Bao tôi ly cafe 🧋 nhé!