Bộ số tam giác (HSG12'18-19)

View as PDF

Points: 200 Time limit: 1.0s Memory limit: 500M Input: stdin Output: stdout

Cho dãy số \(A\) gồm \(n\) phần tử nguyên dương \(A_1, A_2, …, A_n\). Mỗi phần tử có giá trị không vượt quá \(10^9\)\(1 \lt n \leq 5000\). Một bộ ba số được gọi là bộ số tam giác, nếu ba số này tạo thành ba cạnh của một tam giác nào đó.

Yêu cầu: Hãy đếm xem trong dãy \(A\) có bao nhiêu bộ số tam giác (\(A_i, A_j, A_k\)) với \(i, j, k\) đôi một khác nhau.

Input

  • Dòng đầu là số \(n\).
  • Dòng tiếp theo là các phần tử của dãy \(A\), mỗi phần tử cách nhau một dấu cách.

Output

  • Ghi ra số lượng bộ số tam giác.

Scoring

  • Subtask \(1\) (\(30\%\) số điểm): \(n \leq 100\).
  • Subtask \(2\) (\(30\%\) số điểm): \(100 \lt n \leq 1000\).
  • Subtask \(3\) (\(40\%\) số điểm): \(1000 \lt n \leq 5000\).

Example

Test 1

Input
5
4 3 1 5 7 
Output
3

Comments


  • 0
    NTR_Slayer    9:10 p.m. 6 oct, 2024

    dùng py thì o(n**2) cũng die 2 test cuối hả ae


    • 4
      chienthancontent    5:32 p.m. 20 may, 2023

      Dùng kỹ thuật Tow Pointer để có O(n^2)!


      • 23
        jumptozero    9:37 a.m. 26 feb, 2021 edited

        Mình xin chia sẻ lời giải bài này như sau:

        • Đầu tiên ta nhận thấy rằng, việc sắp xếp lại mảng \(a\) đã cho không làm ảnh hưởng đến kết quả bài toán, vì dù sắp xếp thế nào đi chăng nữa thì ta vẫn tìm được \(3\) chỉ số \((i,j,k)\) thoả mãn yêu cầu bài toán.

        • Vậy chúng ta sắp xếp lại có ý nghĩa gì ? Thực ra việc này sẽ giúp ta dễ dàng tìm kiếm nhị phân, làm giảm độ phức tạp của bài toán.

        Ta có nhận xét như sau:

        • Vì mảng \(a\) đã được sắp xếp, nên ta có: \(a[1]<=a[2]<=...<=a[n]\). Khi đó, xét một bộ \(1\le i<j<k\le n\) bất kì, thì ta đã có sẵn hai bất đẳng thức sau:

        Đó là:

        \(\left\{\begin{matrix} a[i]+a[k]>a[j] \\ a[j]+a[k]>a[i]\end{matrix}\right.\), (vì \(0<a[i]<=a[j]<=a[k]\))

        Và để bộ số \((a[i],a[j],a[k])\) là ba cạnh của tam giác, thì ta chỉ việc kiểm tra xem \(a[i]+a[j]> a[k]\) hay không ?

        Và để đếm xem có bao nhiêu bộ số thoả mãn như vậy, ta làm như sau:

        Bước 1: Ta đi xét tất cả các cặp \(1\le i<j<n-1\). Gọi \(sum(i,j)=a[i]+a[j]\).

        Bước 2: Chúng ta sẽ dùng tìm kiếm nhị phân trong đoạn \([j+1,n]\) để đếm xem có bao nhiêu chỉ số \(k\in [j+1,n]\) thoả mãn \(sum(i,j)>a[k]\) là xong.

        Độ phức tạp của bài toán này là : \(O(n^2.log(n))\)

        Các bạn có thể tham khảo code của mình tại đây: Link

        1 reply