Kaninho và bài toán sushi

Xem PDF

Điểm: 550 Thời gian: 2.0s Bộ nhớ: 256M Input: bàn phím Output: màn hình

\(N\) cái đĩa , được đánh số \(1,2,3,\cdots,N\). Ban đầu, với mỗi \(i(1 \leq i \leq N)\), cái đĩa thứ \(i\)\(a_i(1 \leq a_i \leq 3)\) miếng sushi.

Kaninho sẽ lặp lại phép toán dưới đây cho đến khi tất cả các miếng sushi trên các đĩa được ăn hết:

Thả con xúc sắc có \(N\) mặt được đánh số \(1,2,3,\cdots,N\) (xác suất xuất hiện \(N\) mặt này là như nhau), và gọi \(i\) là mặt của con xúc sắc sau khi thả. Nếu có một vài miếng sushi trên đĩa thứ \(i\), Kaninho sẽ ăn 1 cái trong số chúng, còn nếu không có cái nào hết, thì Kaninho sẽ không làm gì cả.
Tìm giá trị kì vọng của số lần thực hiện phép toán trên trước khi tất cả các miếng sushi trên các đĩa được ăn hết.

Input

  • Dòng thứ nhất chứa số nguyên \(N(1 \leq N \leq 300)\)
  • Dòng thứ hai chứa \(N\) số \(a_i(1 \leq a_i \leq 3\))

Output

  • In ra giá trị kì vọng cần tìm. (gọi \(x\) là đáp án của bạn và \(y\) là đáp án của bài toán thì đáp án \(x\) được chấp nhận nếu \(|x−y|<10^{−9}\)

Example

Test 1

Input
3
1 1 1 
Output
5.5
Note

Giá trị kì vọng của số phép toán trước khi miếng sushi thứ nhất được ăn là \(1\). Sau đó, giá trị kì vọng của số phép toán trước khi miếng sushi thứ \(2\) được ăn là \(1.5\). Sau đó, giá trị kì vọng của số phép toán trước khi miếng sushi thứ \(3\) được ăn là \(3\). Như vậy, giá trị kì vọng tổng cộng của số phép toán cần thực hiện là \(1+1.5+3=5.5\)


Bình luận


  • 1
    dthien2212    6:47 p.m. 3 Tháng 8, 2020

    Mọi người có thể cho em xin thêm test mẫu không ạ,em đọc hoài vẫn không hiểu đề @@


    • 0
      vinhntndu    7:30 p.m. 3 Tháng 8, 2020

      INPUT

      5

      1 3 5 7 6

      OUTPUT

      15.6250000000


      • 0
        tuanlinh    7:37 p.m. 3 Tháng 8, 2020

        cho em hỏi với VD:

        n=3
        1 2 3
        

        thì làm sao anh


      • 0
        tuanlinh    7:34 p.m. 3 Tháng 8, 2020

        1<=a[i]<=3 mà :v

      4 bình luận nữa