Atcoder Educational DP Contest J - Sushi

View as PDF

Submit solution


Points: 0.50 (partial)
Time limit: 2.0s
Memory limit: 1G
Input: stdin
Output: stdout

Suggester:
Problem source:
Atcoder Educational DP Contest
Problem type
Allowed languages
C, C++, Java, Kotlin, Pascal, PyPy, Python, Scratch

Cho ~N~ cái đĩa được đánh số ~1,2,...,N~. Trước khi bắt đầu, đĩa thứ ~i~ ~(1 \leq i \leq N)~ có ~a_{i}~ ~(1 \leq a_{i} \leq 3)~ miếng sushi.

Taro sẽ thực hiện hành động sau ở mỗi lượt cho tới khi cậu ấy ăn hết tất cả các miếng sushi:

  • Đổ một cục xúc xắc ~N~ mặt đánh số ~1,2,…,N~ với cùng xác suất xuất hiện. Gọi ~i~ là số xuất hiện. Nếu có bất kỳ miếng sushi nào trên đĩa thứ ~i~ thì ăn một miếng trong số chúng, nếu đĩa trống thì không làm gì cả.

Tìm giá trị kỳ vọng của số lượt Taro cần thực hiện cho tới khi cậu ấy ăn hết tất cả các miếng sushi.

Input

Dòng đầu tiên chứa số nguyên dương ~N~ ~(1 \leq N \leq 300)~

Dòng tiếp theo chứa ~N~ số nguyên ~a_{i}~ ~(1 \leq a_{i} \leq 3)~

Output

In ra giá trị kỳ vọng của số lượt Taro cần thực hiện cho tới khi cậu ấy ăn hết tất cả các miếng sushi. Kết quả in ra được coi là chính xác nếu sai số tuyệt đối với đáp án không vượt quá ~10^{-9}~.

Sample 1

Input
3
1 1 1
Output
5.5
Giải thích
  • Đầu tiên, giá trị kỳ vọng của số lượt Taro cần thực hiện để ăn được miếng sushi thứ nhất là ~1~.
  • Sau khi ăn miếng thứ nhất, giá trị kỳ vọng của số lượt Taro cần thực hiện để ăn được miếng sushi thứ hai là ~1.5~.
  • Sau khi ăn miếng thứ hai, giá trị kỳ vọng của số lượt Taro cần thực hiện để ăn được miếng sushi thứ ba là ~3~.

Do đó, giá trị kỳ vọng của số lượt Taro cần thực hiện để ăn hết tất cả các miếng sushi là ~1+1.5+3=5.5~.

Sample 2

Input
1
3
Output
3
Giải thích:

Kết quả in ra ví dụ như 3.00, 3.000000003 and 2.999999997 đều được coi là chình xác.

Sample 3

Input
2
1 2
Output
4.5

Sample 4

Input
10
1 3 2 3 3 2 3 2 1 3
Output
54.48064457488221

Comments

Please read the guidelines before commenting.


There are no comments at the moment.