\(\color{#ff0000}{\text{Spoiler Alert}_{{}_{{}^{{}^{v2.6}}}}}\)

\(\color{#ff0000}{\text{Khuyến khích bạn đọc trước khi đọc phần lời giải xin hãy thử code ra thuật của mình dù nó có sai hay đúng}}\)

\(\color{#ff0000}{\text{Sau đó từ phần bài giải và thuật toán trước đó mà đối chiếu, rút nhận xét với thuật của mình và thu được bài học (không lãng phí thời gian đâu).}}\)

\(\color{#ff0000}{\text{Mình xin rút kinh nghiệm và chấn chỉnh bản thân nếu trong editorial có gì sai sót, và bạn có thể gửi feedback }}\) ở đây

\(\color{#300000}{\text{Hint 1 <Cày trâu>}}\)

• Ta sẽ duyệt qua từng cặp \((a, b)\) và kiêm tra nếu \((a, b, c)\) tạo thành bộ ba số tam giác ta sẽ tăng biến đếm

Gọi hàm \(isTriangle(a, b, c) = (a + b > c)\text{ and }(b + c > a)\text{ and }(c + a > b)\text{ and }(a > 0)\text{ and }(b > 0)\text{ and }(c > 0)\) trả giá trị \(1\) khi nó đúng (a, b, c là bộ ba số tam giác) và trả về \(0\) khi nó sai

Kết quả cần tính là \(res = \underset{a \in [1, c)}{\Sigma}\underset{b \in [a, c)}{\Sigma}isTriangle(a, b, c)\) và lúc này thỏa \((a, b < c)\)

\(\color{#88B4B4}{\text{Code tham khảo<Time Limit Exceed> }}\): Cày trâu

\(^{^{\color{#7f5f3f}{\text{Complexity : }} O(c^2)\ \color{#7f5f3f}{\text{time}}\ ||\ O(1)\ \color{#7f5f3f}{\text{memory}}}}\)

bool isTriangle(int a, int b, int c) { return a + b > c && b + c > a && c + a > b && a > 0 && b > 0 && c > 0; }
int main()
{
    int c;
    cin >> c;

    int res = 0;
    for (int a = 1; a < c; ++a)
        for (int b = a; b < c; ++b)
            if (isTriangle(a, b, c))
                res++;

    cout << res;
    return 0;
}

\(\color{#300000}{\text{Hint 2 <Toán học>}}\)

• Từ đề bài, ta có \(c\) là cạnh huyền.

Nên khi duyệt các canh \(a < c\). Ta sẽ đếm số cạnh \(b\) thỏa \(c > b \geq a\) và \(b > c - a\)

Kết quả là số số \(b\) trong đoạn \([a, c) \cap (c - a, +oo) = [max(c - a + 1, a), c)\) (giả sử khi \(l > r\) thì \([l, r]\) rỗng)

Số số nguyên trong đoạn \([l, r)\) khi \(l \leq r\) là \(r - l\) và khi \(l > r\) là \(0\). Nên gộp lại ta được kết quả \(max(0, r - l)\)

Vậy kết quả bài toán là \(res = \underset{a \in [1, c)}{\Sigma}max(0, c - d)\) với \(d = max(c - a + 1, a)\)

\(\color{#009933}{\text{Code tham khảo<Accepted> }}\): Toán học

\(^{^{\color{#7f5f3f}{\text{Complexity : }} O(c)\ \color{#7f5f3f}{\text{time}}\ ||\ O(1)\ \color{#7f5f3f}{\text{memory}}}}\)

int main()
{
    int c;
    cin >> c;

    ll res = 0;
    for (int a = 1; a < c; ++a)
    {
        int d = max(a, c - a + 1);
        int v = max(0, c - d);
        res += v;
    }

    cout << res;
    return 0;
}

\(\color{#9000ff}{\text{Question}}\)

• Bạn có thể giải bài này trong \(O(1)\) chứ

Gợi ý: Kết quả có dạng \(\frac{c}{d} \times (c - \frac{c}{d}) - \frac{c}{d}\) với \(d\) là một hằng số khác \(0\)

• Link bài khó hơn:http://lqdoj.edu.vn/problem/cnttriangle2