Bộ số tam giác (HSG12'18-19)
Xem PDF
Điểm:
200
Thời gian:
1.0s
Bộ nhớ:
500M
Input:
bàn phím
Output:
màn hình
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\) và \(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
Bình luận
dùng py thì o(n**2) cũng die 2 test cuối hả ae
Dùng kỹ thuật Tow Pointer để có O(n^2)!
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:
Đó 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