Nhà toán học Italien

Tác giả:

Dạng bài

Điểm: 300 (p) Thời gian: 1.0s Bộ nhớ: 1G Input: bàn phím Output: màn hình

Có một nhà toán học Italien đang nghiên cứu tính chất của một dãy số. Anh ấy có một dãy số gồm \(n\) số nguyên. Anh ấy bốc ra một lần \(3\) số bất kì trong dãy (không quan trọng thứ tự bốc \(3\) số này) và muốn biết xác suất để \(3\) số vừa bốc là một bộ số ziczac.

Bộ số ziczac là bộ số gồm \(3\) số \((i,j,k)\) sao cho \(A[i]>A[j]<A[k]\) và \(1 \leq i<j<k \leq n.\)

Input

Dòng đầu tiên là số n.
Dòng tiếp theo là dãy gồm n số nguyên.

Output

Gồm một dòng duy nhất là xác suất cần tìm, làm tròn đến chữ số thập phân thứ \(6\).

Constraints

\(0 \leq A_i \leq 10 ^ 9\)

Scoring

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

Example

Test 1

Input

4
5 3 1 3

Output

0.500000

Note

Các bộ số có thể có: \((1,2,3); (1,2,4); (1,3,4); (2,3,4)\)

Trong đó \((2,3,4) (1,3,4)\) là một bộ số ziczac.

Vậy xác suất là \(2/4 = 0 \cdot 5\)

Bình luận

0

SPyofgame 6:56 p.m. 23 Tháng 7, 2020

Editorial is being written

3
jumptozero 9:31 p.m. 17 Tháng 6, 2020 ← đã chỉnh sửa →
Mình xin chia sẻ lời giải bài này như sau:

Gọi \(\Omega\) là không gian mẫu của bài toán. Khi đó ta dễ dàng tính được: \(|\Omega|=\binom{n}{3}=\frac{n(n-1)(n-2)}{6}\)

Gọi \(\Omega_A\) là biến cố xảy ra bộ số ziczac, khi đó ta tính \(|\Omega_A|\) như sau:

Ta có: \(|\Omega_A|=\sum\limits_{j=2}^{n-1}X_jY_j\).

Trong đó:

\(X_j\) là số các số \(A[i]\)thỏa mãn \(A[i]>A[j](\forall 1\le i<j)\) và \(Y_j\) là số các số \(A[k]\)thỏa mãn \(A[j]<A[k](\forall j<k\le n)\).

Ta dễ dàng tính \(X_j,Y_j\) trong thời gian \(O(n)\).

Như vậy ta có thể dễ dàng tính \(|\Omega_A|\) trong thời gian \(O(n^2)\).

Vậy đáp án bài toán là: \(P=\frac{|\Omega_A|}{|\Omega|}\)

Mọi người có thể tham khảo code mình tại \(\href{https://ideone.com/3tCVaK}{đây}\)

Nếu có gì sai hoặc khó hiểu , mọi người cứ comment nhé !
1 phản hồi