Nhà toán học Italien

Xem PDF
Tất cả bài nộp
Các bài nộp tốt nhất
Xem hướng dẫn
Tác giả:
corona
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


  • 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é !

    • 0
      SPyofgame    9:32 p.m. 17 Tháng 6, 2020 ← đã chỉnh sửa

      Bài này quy hoạch động được không anh OwO


      • 0
        jumptozero    10:11 p.m. 17 Tháng 6, 2020

        Mình cũng không biết nữa, không biết thuật chuẩn bài này là như thế nào !

      1 bình luận nữa