Đĩa Sushi May Mắn
Points
28
AC Rate
0.0%
Time limit
2.0 s
Memory limit
256M
Group
dp
Đề bài
Có $N$ chiếc đĩa đặt trên bàn, đánh số từ $1$ đến $N$. Ban đầu, đĩa thứ $i$ có $a_i$ miếng sushi ($a_i \in {1, 2, 3}$).
Mỗi bước, Bình tung một con xúc xắc đều $N$ mặt để chọn ngẫu nhiên một số $i \in [1, N]$ (mỗi số có xác suất $\frac{1}{N}$). Nếu đĩa thứ $i$ còn ít nhất $1$ miếng sushi, Bình ăn $1$ miếng từ đĩa đó; nếu đĩa thứ $i$ đã hết sushi, Bình không làm gì cả.
Hãy tính kỳ vọng số bước tung xúc xắc cho đến khi tất cả các đĩa đều hết sushi.
Dữ liệu vào
- Dòng đầu tiên chứa số nguyên $N$ ($1 \le N \le 300$).
- Dòng thứ hai chứa $N$ số nguyên $a_1, a_2, \dots, a_N$ ($1 \le a_i \le 3$).
Dữ liệu ra
- In ra một số thực duy nhất là kỳ vọng số bước cần tìm. Kết quả được chấp nhận nếu sai số tuyệt đối hoặc tương đối không vượt quá $10^{-9}$.
Ví dụ
Input
3
1 1 1
Output
5.5000000000
Giải thích
Với 3 đĩa mỗi đĩa 1 miếng, kỳ vọng là $\frac{3}{3} + \frac{3}{2} + \frac{3}{1} = 5.5$.
Giới hạn
- $1 \le N \le 300$
- $1 \le a_i \le 3$
- Thời gian: 2 giây
- Bộ nhớ: 256 MB
Community Discussion