Kaninho và bài toán sushi

Xem PDF



Tác giả:
Dạng bài
Đ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


  • 0
    WuTan 8:18 p.m. 16 Tháng 8, 2020

    hiểu gì chết liền luôn :((


    • 0
      SPyofgame 9:26 p.m. 6 Tháng 8, 2020

      Bài này là về expected value là chủ yếu :))))


      • 1
        HMD 12:20 a.m. 5 Tháng 8, 2020

        giải thích cho mình rõ hơn cái test đề đc ko ạ

        tại sao miếng đầu tiên độ kì vọng = 1

        tại sao miếng t2 = 1.5

        tại sao miếng t3 = 3

        Mình cảm ơn trước 😊


        • 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 đề @@

          1 phản hồi

          • 1
            Vinht1k60 10:20 a.m. 3 Tháng 8, 2020

            Mình không hiểu để lắm , giá trị kì vọng tính như thế nào , ai có thể nói rõ hơn được không ạ?

            1 phản hồi