2024-2025 Nghệ An¶

Câu 1: Biểu thức có giá trị là số nguyên tố (5.0 điểm)¶

Đề bài¶

Chỗ này lượt bỏ phần râu ria.

Cho số nguyên dương \(n (1 \le n \le 10^6)\).

Xét biểu thức: \(p = x + 2y\).

Yêu cầu: Tìm số lượng cặp số nguyên dương \((x, y)\) sao cho:

\(0 \le x, y \le n\)
\(p\) là một số nguyên tố.

Dữ liệu: Cho trong tệp văn bản BIEUTHUCNT.INP gồm một số nguyên dương \(n\).

Kết quả: Ghi ra tệp văn bản BIEUTHUCNT.OUT gồm một số nguyên dương là giá trị của \(s\). Trong đó \(s\) là số lượng các cặp số nguyên dương \((x, y)\) thỏa mãn hai điều kiện trên.

Ví dụ:

BIEUTHUCNT.INP	BIEUTHUCNT.OUT	Giải thích
4	6	Có 6 cặp \((x, y)\) thỏa mãn: \((x, y) = (1,1), p = x + 2y = 3\) \((x, y) = (1,2), p = x + 2y = 5\) \((x, y) = (1,3), p = x + 2y = 7\) \((x, y) = (3,1), p = x + 2y = 5\) \((x, y) = (3,2), p = x + 2y = 7\) \((x, y) = (3,4), p = x + 2y = 11\)

Giới hạn:

Có 80% số test ứng với \(n \le 10^3\).
Có 20% số test còn lại ứng với \(10^3 \lt n \le 10^6\).

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

Bước 1: Để xác định \(p = x + 2y\) có phải là nguyên tố không, ta tạo sàng Eratosthenes đánh dấu các số nguyên tố trước.

Trong đó, vì \(x, y \le n\) nên \(x + 2y \le 3n\). Ta khởi tạo mảng S (sieve: sàng) gồm \(3n + 1\) phần tử.

C++Python

void sieve()
{
    // Giả sử tất cả đều là số nguyên tố
    S.resize(3 * n + 1, 1);

    // 0 và 1 không phải nguyên tố
    S[0] = S[1] = 0;

    // Duyệt từ 2 đến 3n
    for (int i = 2; i * i < 3 * n + 1; ++i)
    {
        // Nếu i là nguyên tố
        if (S[i] == 1)
        {
            // thì các bội j của i đang xét không còn nguyên tố nữa
            for (int j = i * i; j < 3 * n + 1; j += i)
            {
                S[j] = 0;         
            }
        }
    }
}

def sieve():
    global n, S

    # Giả sử tất cả đều là số nguyên tố
    S = [1] * (3 * n + 1)

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

    # Duyệt từ 2 đến 3n
    i = 2
    while i * i < 3 * n + 1:
        # Nếu i là nguyên tố
        if S[i] == 1:
            # thì các bội j của i đang xét không còn nguyên tố nữa
            for j in range(i * i, 3 * n + 1, i):
                S[j] = 0
        i += 1

Bước 2: Để đếm số cặp \((x, y)\), ta dùng hai vòng lặp lồng nhau để duyệt \(x\) và \(y\).

C++Python

    int cnt = 0;
    int p;

    // Duyệt tất cả x và y
    for (int x = 1; x < n + 1; ++x)
    {
        for (int y = 1; y < n + 1; ++y)
        {
            p = x + 2 * y;
            if (S[p] == 1) cnt += 1;
        }
    }

    cnt = 0

    # Duyệt tất cả x và y
    for x in range(1, n + 1):
        for y in range(1, n + 1):
            p = x + 2 * y
            if S[p] == 1:
                cnt += 1

    return cnt

Mã nguồn¶

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

Câu 2: Tặng quà (4.0 điểm)¶

Đề bài¶

Buổi lễ bế mạc của một kỳ thi lập trình danh giá được tổ chức rất hoành tráng, đã đem lại nhiều cảm xúc và bất ngờ cho người tham dự. Có \(n\) học sinh tham gia cuộc thi danh giá này, trong đó có đội tuyển Tín học của An. Các em đều thấy rất thú vị trong phần tặng quà của buổi lễ bế mạc. Phần tặng quà được điều khiển bởi hai con robot. Các em lần lượt lên sân khấu nhận quà, đến lượt học sinh thứ \(i\) (với \(i = 1, 2, ..., n\)), robot thứ nhất sẽ chọn ngẫu nhiên một món quà có giá trị là \(a_i\), robot thứ hai sẽ hỏi lại với câu hỏi: "Món quà có giá trị nhỏ nhất và khác với giá của \(i\) món quà trước đó nhất đã tặng có giá bao nhiêu?". Robot thứ hai đã biết kết quả của câu trả lời đúng là \(b_i\). Nếu học sinh trả lời đúng sẽ nhận ngay một món quà đặc biệt của robot thứ hai. Biết rằng, giá của các món quà đều là số nguyên dương.

Yêu cầu: Hãy tìm \(b_1, b_2, ..., b_n\).

Dữ liệu: Cho trong tệp văn bản TANGQUA.INP gồm:

Dòng 1 ghi số nguyên dương \(n (1 \le n \le 10^6)\).
Dòng 2 ghi n số nguyên dương \(a_1, a_2, ..., a_n (1 \le a_i \le 10^6)\) lần lượt là giá của \(n\) món quà mà robot thứ nhất tặng cho \(n\) học sinh.

Kết quả: Ghi ra tệp văn bản TANGQUA.OUT gồm \(n\) số nguyên dương \(b_1, b_2, ..., b_n\). Các số được ghi trên một dòng và cách nhau bởi dấu cách.

Ví dụ:

TANGQUA.INP	TANGQUA.OUT	Giải Thích
5 1 2 3 5 7	2 3 4 4 4	Lượt học sinh 1: \([a_1] = [1] \rightarrow b_1 = 2\) Lượt học sinh 2: \([a_1, a_2] = [1, 2] \rightarrow b_2 = 3\) Lượt học sinh 3: \([a_1, a_2, a_3] = [1, 2, 3] \rightarrow b_3 = 4\) Lượt học sinh 4: \([a_1, a_2, a_3, a_4] = [1, 2, 3, 5] \rightarrow b_4 = 4\) Lượt học sinh 5: \([a_1, a_2, a_3, a_4, a_5] = [1, 2, 3, 5, 7] \rightarrow b_5 = 4\)
5 2 1 5 4 3	1 3 3 3 6	Lượt học sinh 1: \([a_1] = [2] \rightarrow b_1 = 1\) Lượt học sinh 2: \([a_1, a_2] = [2, 1] \rightarrow b_2 = 3\) Lượt học sinh 3: \([a_1, a_2, a_3] = [2, 1, 5] \rightarrow b_3 = 3\) Lượt học sinh 4: \([a_1, a_2, a_3, a_4] = [2, 1, 5, 4] \rightarrow b_4 = 3\) Lượt học sinh 5: \([a_1, a_2, a_3, a_4, a_5] = [2, 1, 5, 4, 3] \rightarrow b_5 = 6\)

Giới hạn:

Có 70% số test thoả mãn \(n \le 10^3; 1 \le a_1 \le a_2 \le ... \le a_n\).
Có 30% số test thoả mãn \(10^3 < n \le 10^6\).

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

Bước 1: Để biết món quà nào đã phát hoặc chưa phát, ta sử dụng mảng tần số, tạm gọi là granted:

granted[giá trị v] == 1: món quà có giá trị v đã được phát.
granted[giá trị v] == 0: món quà có giá trị v chưa được phát.

C++Python

    // Khởi tạo mảng tần số granted, dùng để đánh dấu những món quà đã phát
    vector<char> granted(1000001, 0);

    # Khởi tạo mảng tần số granted, dùng để đánh dấu những món quà đã phát
    granted = [0] * 1000001

Bước 2: Gọi least = 1 là giá trị v nhỏ nhất. Nếu granted[least] cứ bằng 1, tức món quà có giá trị least đã phát, thì ta tăng least lên cho đến khi gặp granted[least] chưa phát.

C++Python

    // Khởi tạo món quá có giá trị nhỏ nhất là 1
    int least = 1;

    // Duyệt tất cả món quà
    for (int i = 0; i < n; ++i)
    {
        // Đánh dấu món quà A[i] đã phát
        granted[A[i]] = 1;

        // Nếu món quà có giá trị least đã được phát
        while (granted[least] == 1)
        {
            // thì tăng least thêm 1
            least += 1;
        }

    # Khởi tạo món quá có giá trị nhỏ nhất là 1
    least = 1

    # Duyệt tất cả món quà
    for a in A:

        # Đánh dấu món quà có giá trị a đã phát
        granted[a] += 1

        # Nếu món quà có giá trị least đã được phát
        # thì tăng least thêm 1
        while granted[least] == 1:
            least += 1

Mã nguồn¶

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