Editorial - Tam giác

Mỗi tam giác đều cần đúng 3 thẻ tre có cùng độ dài.

Nếu một độ dài ~v~ xuất hiện ~cnt[v]~ lần thì số tam giác đều tạo được từ riêng độ dài đó là:

~\left\lfloor \dfrac{cnt[v]}{3} \right\rfloor~

Do các độ dài khác nhau không thể ghép chung để tạo tam giác đều, ta cộng kết quả của từng độ dài:

• ~x = \sum\limits_v \left\lfloor \dfrac{cnt[v]}{3} \right\rfloor~
• ~y = n - 3x~

Trong đó:

• ~x~ là số tam giác đều tối đa tạo được;
• ~y~ là số thẻ còn lại.

Thuật toán

1. Đếm số lần xuất hiện của từng độ dài.
2. Với mỗi độ dài từ ~1~ đến ~2000~, cộng ~cnt[v] / 3~ vào đáp án.
3. Tính số thẻ còn lại bằng ~n - 3x~.

Độ phức tạp

• Đếm tần suất: ~O(n)~
• Duyệt các giá trị độ dài: ~O(2000)~

Tổng cộng: ~O(n)~.

Code C++ tham khảo

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;

    vector<int> cnt(2001, 0);
    for (int i = 0; i < n; i++) {
        int x;
        cin >> x;
        cnt[x]++;
    }

    long long x = 0;
    for (int v = 1; v <= 2000; v++) {
        x += cnt[v] / 3;
    }

    long long y = n - 3 * x;
    cout << x << ' ' << y << '\n';
    return 0;
}