Hướng dẫn cho Bài 2: Kết hoa (TS10 Ninh Bình thi thử - 2026)

Chỉ sử dụng khi thực sự cần thiết như một cách tôn trọng tác giả và người viết hướng dẫn này.

Chép code từ bài hướng dẫn để nộp bài là hành vi có thể dẫn đến khóa tài khoản.

Tóm tắt đề bài

Cho \(n\) cánh hoa, cánh thứ \(i\) có độ dài \(a_i\). Một bông hoa hợp lệ được tạo thành từ đúng 3 cánh hoa có cùng độ dài. Mỗi cánh hoa chỉ được dùng một lần.

Tìm \(x\): Số bông hoa tối đa có thể kết được.
Tìm \(y\): Số cánh hoa còn dư sau khi đã kết tối đa số bông hoa.

Phân tích

Điều kiện: \(n \leq 10^6\), \(a_i \leq 2000\).
Nhận xét:
- Để tạo được một bông hoa từ các cánh hoa có cùng độ dài \(L\), ta cần ít nhất 3 cánh hoa độ dài \(L\).
- Nếu có \(count\) cánh hoa cùng độ dài \(L\), số bông hoa tối đa tạo được từ loại cánh này là \(\lfloor count / 3 \rfloor\) (phần nguyên của phép chia \(count\) cho 3).
- Số cánh hoa dư ra từ loại này là \(count \pmod 3\).
- Tổng số bông hoa \(x\) sẽ là tổng số bông hoa tạo được từ tất cả các loại độ dài khác nhau.
- Tổng số cánh hoa dư \(y\) sẽ là tổng số cánh dư của từng loại cộng với các cánh hoa của những loại có số lượng ít hơn 3.

Cách làm đơn giản (Brute Force)

Ý tưởng

Sắp xếp mảng các cánh hoa theo thứ tự tăng dần. Sau đó duyệt mảng để đếm số lượng các cánh hoa có cùng độ dài liên tiếp nhau. Với mỗi nhóm cùng độ dài, tính số bông hoa và số cánh dư.

Độ phức tạp

Thời gian: \(O(n \log n)\) do thao tác sắp xếp.
Đánh giá: Với \(n = 10^6\), \(O(n \log n)\) vẫn có thể vượt qua trong giới hạn thời gian, nhưng có thể tối ưu hơn dựa vào giới hạn của \(a_i\).

Code Brute Force

C++

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n;
    cin >> n;
    vector<int> a(n);
    for (int i = 0; i < n; i++) cin >> a[i];

    sort(a.begin(), a.end());

    long long total_flowers = 0;
    long long total_remain = 0;

    int i = 0;
    while (i < n) {
        int j = i;
        while (j < n && a[j] == a[i]) {
            j++;
        }
        int count = j - i;
        total_flowers += count / 3;
        total_remain += count % 3;
        i = j;
    }

    cout << total_flowers << " " << total_remain << endl;
    return 0;
}

Python

import sys

def solve():
    n = int(sys.stdin.readline())
    if n == 0:
        print(0, 0)
        return
    a = list(map(int, sys.stdin.readline().split()))
    a.sort()

    total_flowers = 0
    total_remain = 0

    i = 0
    while i < n:
        j = i
        while j < n and a[j] == a[i]:
            j += 1
        count = j - i
        total_flowers += count // 3
        total_remain += count % 3
        i = j

    print(f"{total_flowers} {total_remain}")

solve()

Hướng giải quyết (Tối ưu)

Nhận xét

Giá trị của \(a_i\) rất nhỏ (\(a_i \leq 2000\)), trong khi \(n\) rất lớn (\(n \leq 10^6\)). Thay vì sắp xếp, ta có thể dùng một mảng tần suất (mảng đếm) để thống kê số lượng cánh hoa của từng loại độ dài.

Thuật toán

Khởi tạo mảng cnt có kích thước \(2001\) để đếm số lần xuất hiện của mỗi độ dài \(a_i\).
Duyệt qua mảng đầu vào, với mỗi \(a_i\), tăng cnt[a_i] lên 1 đơn vị.
Duyệt từ \(1\) đến \(2000\):
- Cộng cnt[i] / 3 vào biến tổng số bông hoa \(x\).
- Cộng cnt[i] % 3 vào biến tổng số cánh dư \(y\).
In ra \(x\) và \(y\).

Độ phức tạp

Thời gian: \(O(n + \max(a_i))\), trong đó \(n\) là số lượng phần tử và \(\max(a_i) = 2000\). Đây là độ phức tạp tối ưu.
Bộ nhớ: \(O(\max(a_i))\) để lưu mảng đếm.

Code tham khảo

C++

#include <bits/stdc++.h>
using namespace std;

// Khai báo mảng đếm toàn cục để tránh tràn bộ nhớ stack
int cnt[2005];

int main() {
    // Tối ưu tốc độ nhập xuất
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n;
    cin >> n;

    for (int i = 0; i < n; i++) {
        int val;
        cin >> val;
        // Đếm số lượng cánh hoa của từng loại độ dài
        if (val <= 2000) {
            cnt[val]++;
        }
    }

    long long x = 0; // Tổng số bông hoa
    long long y = 0; // Tổng số cánh dư

    for (int i = 1; i <= 2000; i++) {
        if (cnt[i] > 0) {
            x += cnt[i] / 3;     // Mỗi 3 cánh cùng loại tạo 1 bông
            y += cnt[i] % 3;     // Số cánh dư của loại này
        }
    }

    cout << x << " " << y << endl;

    return 0;
}

Python

import sys

def solve():
    # Đọc n
    line1 = sys.stdin.readline()
    if not line1:
        return
    n = int(line1.strip())

    # Đọc mảng a
    line2 = sys.stdin.readline()
    if not line2:
        a = []
    else:
        a = list(map(int, line2.split()))

    # Sử dụng mảng đếm (tối đa độ dài là 2000)
    cnt = [0] * 2001
    for val in a:
        cnt[val] += 1

    total_flowers = 0
    total_remain = 0

    # Duyệt qua các độ dài có thể có
    for count in cnt:
        if count > 0:
            total_flowers += count // 3
            total_remain += count % 3

    print(f"{total_flowers} {total_remain}")

if __name__ == "__main__":
    solve()

Bình luận

Tải bình luận...

Không có bình luận nào.