Học sinh giỏi 9 Khánh Hoà 2023 - 2024¶

Bài 1: Đếm gạo¶

Đề bài¶

Nấm thích truyện cổ tích. Đêm qua, Nấm nằm mơ về Lọ Lem. Lọ Lem không bị mụ dì ghẻ bắt phân loại đậu nữa mà bắt nhặt gạo.

Có rất nhiều gạo trong kho, các hạt gạo được đánh số thứ tự là số nguyên liên tiếp từ \(a\) đến \(b\). Mụ bắt nàng phải nhặt ra các hạt gạo có số thứ tự là bội của một số \(k\) cho trước. Đồng thời sau khi nhặt xong phải cho biết số lượng hạt gạo nhặt được.

Việc nhặt gạo thì đơn giản, bầy chim đã giúp nhặt xong. Nhiệm vụ của Lọ Lem là đếm số lượng. Thật không may, chưa đếm xong thì Nấm đã tỉnh dậy. Nấm rất muốn có câu trả lời cho Lọ Lem.

Yêu cầu: Hãy trả lời giúp Nấm là có bao nhiêu hạt gạo.

Dữ liệu vào: DEMGAO.INP

Gồm ba số nguyên dương \(a, b\) và \(k\) trên cùng một dòng \((1 \le a \le b < 10^{18}; 1 \le k \le 10^{18})\).

Kết quả: DEMGAO.OUT

Một số nguyên lẻ duy nhất là kết quả cần tìm.

Ví dụ:

DEMGAO.INP	DEMGAO.OUT	Giải thích
3 10 5	2	Hai hạt gạo được nhặt là hạt số có thứ tự 5 và số thứ tự 10.
6 9 5	0	Không có hạt nào thoả mãn yêu cầu.

Ràng buộc:

70% số test tương ứng với 70% số điểm có \(1 \le a \le b < 10^6\).
30% số test còn lại tương ứng 30% điểm số kkhông có ràng buộc gì thêm.

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

Ý tưởng chính¶

Với \(n\) là một số nguyên dương, các bội của \(k\) mà không vượt quá \(n\) bao gồm những số sau: \(1k, 2k, 3k, ..., qk\)

Ta có: \(qk \le n \Rightarrow q \le \frac{n}{k}\).

Vì \(q\) có thể là các giá trị trong đoạn \([1..q]\) nên \(q\) cũng là số lượng các bội của \(k\) mà không vượt quá \(n\).

Như vậy, để tính số lượng bội của \(k\) trong đoạn \([a..b]\), ta thực hiện như sau:

Tính số lượng bội của \(k\) trong đoạn \([1..b]\): \(\frac{b}{k}\) \((1)\)
Tính số lượng bội của \(k\) trong đoạn \([1..a - 1]\): \(\frac{a - 1}{k}\) \((2)\)
Số lượng bội của \(k\) trong đoạn \([a..b]\) là hiệu của \((1)\) và \((2)\).

Viết chương trình¶

C++Python

    // Số lượng bội của k trong phạm vi [1..b]
    lli count_b_k = b / k;

    // Số lượng bội của k trong phạm vi [1..a - 1]
    lli count_a_1_k = (a - 1) / k; 

    // Số lượng bội của k trong phạm vi [a..b]
    count_multiples = count_b_k - count_a_1_k;

    # Số lượng bội của k trong phạm vi [1..b]
    count_b_k = b // k

    # Số lượng bội của k trong phạm vi [1..a - 1]
    count_a_1_k = (a - 1) // k 

    # Số lượng bội của k trong phạm vi [a..b]
    count_multiples = count_b_k - count_a_1_k 

Mã nguồn¶

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

Bài 2: Từ dài¶

Đề bài¶

Một từ được định nghĩa là một ký tự hoặc một dãy ký tự liên tiếp nhau và không chứa khoảng trắng. Độ dài của một từ là số ký tự có trong từ đó.

Cho xâu gồm các ký tự A..Z, a..z, 0..9 và ký tự khoảng trắng.

Yêu cầu: Tìm độ dài của từ có nhiều ký tự nhất và từ tương ứng với độ dài đó.

Dữ liệu vào: TUDAI.INP

Một dòng duy nhất chứa xâu. Độ dài xâu không quá 255 ký tự và trong xấu có ít nhất một từ.

Kết quả: TUDAI.OUT

Dòng 1: độ dài của từ có nhiều ký tự nhất, tức độ dài lớn nhất.
Dòng 2: từ mà có độ dài lớn nhất.

Nếu có nhiều từ có cùng độ dài lớn nhất thì ghi từ có độ dài lớn nhất sau cùng trong xâu.

Ví dụ:

TUDAI.INP	TUDAI.OUT
Khanh Hoa que huong toi	5 huong

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

Ý tưởng chính¶

Để xử lý từng từ trong chuỗi input:

Đối với C++, ta dùng kiểu dữ liệu stringstream. stringstream giúp đọc các ký tự liên tiếp nhau cho đến khi gặp khoảng trắng hoặc đến khi hết dữ liệu.
Trong Python, ta dùng hàm split() để tách chuỗi thành list các từ.

Viết chương trình¶

C++Python

    // Khởi tạo stringstream từ chuỗi line
    stringstream ss(line);

    string word;

    // Đọc từng từ trong ss vào word
    while (ss >> word)
    {
        int len = word.length();
        if (len >= max_length)
        {
            max_length = len;
            longest_word = word;
        }
    }

    # Tách chuỗi line thành list gồm các từ
    words = line.split()

    # Duyệt từng từ trong list words
    for word in words:
        length = len(word)

        if length >= max_length:
            max_length = length
            longest_word = word

Mã nguồn¶

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

Bài 3: Cửa sổ¶

Đề bài¶

Tí đang chơi trò ghép nhà từ những que tính. Phần căn nhà đã được ghép xong, chỉ còn thiếu một cửa số hình chữ nhật.

Hiện tại, Tí còn dư n que tính. Các que được đánh số thứ tự từ \(1\) đến \(n\). Que thứ \(i\) có độ dài \(a_i\).

Tí muốn ghép được cửa sổ càng to càng tốt. Một cửa sổ sẽ được ghép từ 4 que.

Yêu cầu: Hãy cho biết chu vi của cửa sổ lớn nhất mà Tí có thể ghép được.

Không bẻ gãy hay chắp nối để thay đổi độ dài que. Hình vuông cũng được xem là hình chữ nhật.

Dữ liệu vào: CUASO.INP

Dòng đầu chứa số nguyên dương \(n (1 \le n \le 10^6)\).
Dòng thứ hai chứ \(n\) số nguyên dương \(a_i (1 \le a_i \le 10^6; 1 \le i \le n)\).

Kết quả: CUASO.INP

Số nguyên duy nhất là chua vi lớn nhất của cửa sổ có thể ghép được. Nếu không thể ghép được thì ghi \(-1\).

Ví dụ:

CUASO.INP	CUASO.OUT	Giải thích
7 3 8 4 3 8 1 1	22	Có 3 cách ghép cửa sổ là: \((8, 3), (3, 1), (8, 1)\). Chu vi lớn nhất là \((8 + 3) \times 2 = 22\).
5 4 9 1 9 3	-1	Không thể ghép được cửa sổ nào.

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

Ý tưởng chính¶

Dùng mảng tần số để lưu số lần xuất hiện của từng độ dài que.
Độ dài nào xuất hiện trên 2 lần thì nạp vào mảng độ dài ứng viên (có thể đem ghép cửa sổ).
Sắp xếp mảng ứng viên giảm dần. Lúc này, hai phần tử đầu tiên chính là hai độ dài lớn nhất, tức làm cho chu vi cửa sổ trở thành lớn nhất.

Viết chương trình¶

Bước 0:

Khởi tạo mảng tần số f và các biến liên quan.

C++Python

const int MAX = 1e6;

int n;

// mảng tần số lưu số lần xuất hiện của một độ dài a[i]
vector<int> f(MAX + 1, 0);

// chu vi lớn nhất
int max_perimeter = -1;

MAX = 1000000

n = 0

# mảng tần số lưu số lần xuất hiện của một độ dài a[i]
f = [0] * (MAX + 1)

# chu vi lớn nhất
max_perimeter = -1

Bước 1:

Cập nhật mảng tần số f.

C++Python

    cin >> n;

    int length;

    // Đọc từng độ dài và cập nhật số lần xuất hiện của từng độ dài
    for (int i = 0; i < n; ++i)
    {
        cin >> length;
        f[length]++;
    }

# Cập nhật số lần xuất hiện của từng độ dài
for a in A:
    f[a] += 1

Bước 2:

Độ dài nào xuất hiện hơn 2 lần thì nạp vào mảng ứng viên candidates.

Nếu xuất hiện 4 lần thì nạp thêm lần nữa, do có thể ghép cửa sổ hình vuông.

C++Python

    // mảng lưu các độ dài ứng viên
    vector<int> candidates;

    // Duyệt mảng tần số f
    for (int length = 1; length < MAX + 1; ++length)
    {
        // Nếu độ dài có hơn 2 que thì nạp độ dài này vào mảng ứng viên
        if (f[length] >= 2)
        {
            candidates.push_back(length);
        }

        // Nếu độ dài có hơn 4 que thì nạp độ dài này vào mảng ứng viên lần nữa
        if (f[length] >= 4)
        {
            candidates.push_back(length);
        }
    }

    # mảng lưu các độ dài ứng viên
    candidates = []

    # Duyệt mảng tần số f
    for length in range(MAX + 1):
        # Nếu độ dài có hơn 2 que thì nạp độ dài này vào mảng ứng viên
        if f[length] >= 2:
            candidates.append(length)

        # Nếu độ dài có hơn 4 que thì nạp độ dài này vào mảng ứng viên lần nữa
        if f[length] >= 4:
            candidates.append(length)   

Bước 3:

Nếu mỗi độ dài (mỗi phần tử) trong mảng ứng viên có đủ 2 loại trở lên thì thực hiện sắp xếp giảm dần. Rồi lấy ra hai phần tử đầu, chính là hai loại độ dài lớn nhất, để tính chu vi lớn nhất.

C++Python

    // Nếu mỗi độ dài ứng viên có đủ 2 loại trở lên
    if (candidates.size() > 1)
    {
        // thì sắp xếp các độ dài giảm dần
        sort(candidates.rbegin(), candidates.rend());

        // Tính chu vi lớn nhất
        max_perimeter = 2 * (candidates[0] + candidates[1]);
    }

    # Nếu mỗi độ dài ứng viên có đủ 2 loại trở lên
    if len(candidates) > 1:
        # thì sắp xếp các độ dài giảm dần
        candidates.sort(reverse=True)

        # Tính chu vi lớn nhất
        max_perimeter = 2 * (candidates[0] + candidates[1])

Mã nguồn¶

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

Bài 4: Số nguyên tố toàn diện¶

Đề bài¶

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

Vốn là người sáng tạo, An đưa ra một khái niệm mới gọi là "số nguyên tố toàn diện". Một số nguyên dương x gọi là số nguyên tố toàn diện nếu thoả mãn đồng thời 3 điều kiện sau:

x là số nguyên tố.
Lần lượt bỏ đi các chữ số bên phải của x thì phần còn lại của nó vẫn là số nguyên tố.
Thêm vào bên phải của x một trong các chữ số từ 0 đến 9, số thu được cũng là số nguyên tố.

Ví dụ: 313 là số nguyên tố toàn diện vì:

313 là nguyên tố.
Bỏ đi số 3 bên phải, ta còn số 31, là số nguyên tố. Bỏ tiếp đi số 1, ta còn số 3, cũng là số nguyên tố.
Thêm số 7 vào sau 313, ta được số 3137 là số nguyên tố.

Yêu cầu: cho dãy A gồm \(n\) số nguyên dương \(a_1, a_2, ..., a_n\) và \(m\) câu hỏi. Mỗi câu hỏi có dạng \((u, v)\) với ý nghĩa: đếm số lượng số nguyên tố toàn diện trong dãy A từ vị trí \(u\) đến \(v\).

Dữ liệu vào: SNTOTD.INP

Dòng đầu chứ số nguyên \(n (1 \le n \le 10^5)\).
Dòng thứ hai chứa \(n\) số nguyên dương \(a_1, a_2, ..., a_n (1 \le a_i \le 10^6; 1 \le i \le n)\).
Dòng thứ ba chứa số nguyên \(m\) là số lượng câu hỏi \((1 \le m \le 10^5)\).
\(m\) dòng tiếp theo, mỗi dòng chứa hai số nguyên dương \(u, v (1 \le u \le v \le n)\).

Kết quả: SNTOTD.OUT

Gồm \(m\) dòng, mỗi dòng là đáp án của một câu hỏi theo thứ tự của các câu hỏi được đưa ra trong dữ liệu vào.

Ví dụ:

SNTOTD.INP	SNTOTD.OUT	Giải thích
6 59 12 57 53 23 313 3 1 3 2 5 3 6	1 1 2	Có 1 số nguyên tố toàn diện là 59 trong đoạn từ 1 đến 3. Có 1 số nguyên tố toàn diện là 23 trong đoạn từ 2 đến 5. Có 2 số nguyên tố toàn diện là 23 và 313 trong đoạn từ 3 đến 6.

Ràng buộc:

70% số test tương ứng với 70% số điểm có \(1 \le n \le 10^3; 1 \le a_i \le 10^3\).
30% số test còn lại tương ứ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ùng sàng Eratosthenes để kiểm tra các điều kiện liên quan đến nguyên tố.
Viết ba hàm kiểm tra ứng với ba điều kiện nguyên tố của đề bài.
Viết một hàm nữa, gọi ba hàm vừa viết trên nhằm xác định số nguyên tố toàn diện.
Dùng mảng cộng dồn (prefix sum) để tính số lượng số nguyên tố toàn diện theo từng truy vấn (câu hỏi).

Viết chương trình¶

Bước 0:

Đặt giới hạn trên cho sàng Eratosthenes và các biến liên quan.

C++Python

// 10^6 * 10 + 9 < 10^7 + 10
const int MAX = 1e7 + 10;

int n;
vector<int> A;
int m;

// Khởi tạo mảng prime để lưu trữ sàng Eratosthenes
vector<char> prime(MAX + 1, 1);

// Mảng chứa các kết quả
vector<int> results;

# 10^6 * 10 + 9 < 10^7 + 10
MAX = 10000010

n = 0
A = []

# Khởi tạo mảng prime để lưu trữ sàng Eratosthenes
prime = [True] * MAX

# Mảng chưa các kết quả
results = []

Bước 1:

Viết hàm để khởi tạo sàng Eratosthenes.

C++Python

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

    // Duyệt các số từ 2 trở đi
    for (int p = 2; p * p < MAX; ++p)
    {
        // Nếu p là số nguyên tố
        if (prime[p] == 1)
        {
            // thì đánh dấu 0 (false) cho các bội số của p
            for (int i = p * p; i < MAX; i += p)
            {
                prime[i] = 0;
            }
        }
    }
}

# Hàm tạo sàng Eratosthenes
def sieve():
    # 0 và 1 không phải nguyên tố
    prime[0] = False
    prime[1] = False

    # Duyệt các số từ 2 trở đi
    for p in range(2, int(math.sqrt(MAX)) + 1):
        # Nếu p là số nguyên tố
        if prime[p] == True:
            # thì đánh dấu False cho các bội số của p
            for i in range(p * p, MAX, p):
                prime[i] = False

Bước 2:

Viết ba hàm kiểm tra từng điều kiện thoả mãn số nguyên tố toàn diện.

C++Python

// Hàm kiểm tra điều kiện 1:
inline bool check_1(int x) // (1)!
{
    // Kiểm tra x có phải là nguyên tố không
    return prime[x] == 1;
}


// Hàm kiểm tra điều kiện 2
inline bool check_2(int x)
{
    int tmp = x / 10;

    // Lần lượt bỏ chữ số bên phải mà vẫn còn nguyên tố
    while (tmp > 0)
    {
        if (prime[tmp] == 0) return false;
        tmp /= 10;
    }

    return true;
}


// Hàm kiểm tra điều kiện 3: thêm chữ số vào bên phải
inline bool check_3(int x)
{
    // Thêm chữ số vào bên phải và số mới vẫn là nguyên tố
    for (int d = 0; d <= 9; ++d)
    {        
        int tmp = x * 10 + d;

        if (tmp <= MAX)
        {
            if (prime[tmp] == 1) return true;
        }
    }

    return false;
}

Từ khoá inline làm cho trình biên dịch thay thế lời gọi hàm bằng toàn bộ đoạn mã của thân hàm tại vị trí gọi hàm.

Mục đích chính là tăng tốc độ thực thi chương trình bằng cách loại bỏ chi phí liên quan đến việc gọi hàm. Chi phí này bao gồm:
- Chuẩn bị stack
- Nhảy (jump)
- Thực thi hàm
- Trả về giá trị
- Dọn dẹp stack
- Nhảy về

# Hàm kiểm tra điều kiện 1:
def check_1(x):
    global prime

    # Kiểm tra x có phải là nguyên tố không
    return prime[x] == True


# Hàm kiểm tra điều kiện 2:
def check_2(x):
    global prime

    tmp = x // 10

    # Lần lượt bỏ chữ số bên phải mà vẫn còn nguyên tố
    while tmp > 0:
        if prime[tmp] == False:
            return False

        tmp = tmp // 10

    return True


# Hàm kiểm tra điều kiện 3:
def check_3(x):
    global prime

    # Thêm chữ số vào bên phải và số mới vẫn là nguyên tố
    for d in range(10):
        tmp = x * 10 + d

        if tmp < MAX:
            if prime[tmp] == True:
                return True

    return False

Bước 3:

Viết hàm kiểm tra số nguyên tố toàn diện bằng cách gọi thực thi ba hàm trên.

C++Python

bool is_comprehensive_prime(int x)
{
    if (check_1(x) == false) return false;

    if (check_2(x) == false) return false;

    if (check_3(x) == false) return false;

    return true;
}

def is_comprehensive_prime(x):
    if check_1(x) == False:
        return False

    if check_2(x) == False:
        return False

    if check_3(x) == False:
        return False

    return True

Bước 4:

Đọc dữ liệu vào, cập nhật giá trị của mảng tổng cộng dồn và tính kết quả của các truy vấn (câu hỏi).

C++Python

    cin >> n;

    // Khởi tạo mảng A
    A.resize(n + 1);

    // Khởi tạo mảng tổng cộng dồn (prefix sum)
    // count_cp[i] lưu số lượng số nguyên tố toàn diện trong phạm vi [1..i]
    vector<int> count_cp(n + 1, 0);

    // Duyệt mảng A
    for (int i = 1; i < n + 1; ++i)
    {
        // Đọc từng phần tử của A
        cin >> A[i];

        // Cập nhật mảng cộng dồn
        count_cp[i] = count_cp[i - 1] + (is_comprehensive_prime(A[i]) ? 1 : 0);
    }

    cin >> m;

    // Khởi tạo mảng chứa kết quả
    results.resize(m, 0);

    int u, v;

    // Duyệt từng truy vấn [u, v]
    for (int i = 0; i < m; ++i)
    {
        // Đọc truy vấn
        cin >> u >> v;

        // Cập nhật kết quả của từng truy vấn dựa trên mảng tổng cộng dồn
        results[i] = count_cp[v] - count_cp[u - 1]; 
    }

    with open(input_file, 'r') as f:
        n = int(f.readline())

        # Đọc các phần tử của mảng A
        A = list(map(int, f.readline().split()))
        A.insert(0, 0)

        # Khởi tạo mảng tổng cộng dồn (prefix sum)
        # count_cp[i] lưu số lượng số nguyên tố toàn diện trong phạm vi [1..i]
        count_cp = [0] * (n + 1)

        # Duyệt mảng A
        for i in range(1, n + 1):
            # Cập nhật mảng cộng dồn
            count_cp[i] = count_cp[i - 1] + (1 if is_comprehensive_prime(A[i]) else 0)

        m = int(f.readline())

        # Khởi tạo mảng chứa kết quả
        results = [0] * m

        # Duyệt từng truy vấn [u, v]
        for i in range(m):
            # Đọc truy vấn
            u, v = map(int, f.readline().split())

            # Cập nhật kết quả của từng truy vấn dựa trên mảng tổng cộng dồn
            results[i] = count_cp[v] - count_cp[u - 1]

Mã nguồn¶

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

Bao tôi ly cafe 🧋 nhé!