Tung đồng xu
Đề bài
Mô tả
Một dãy các lần tung đồng xu có thể được mã hóa thành một xâu nhị phân: '0' là mặt ngửa, '1' là mặt sấp. Cho một xâu mã hóa , ta tung đồng xu liên tục cho đến khi xuất hiện trong dãy kết quả thì dừng lại.
Gọi là số lần tung đồng xu cần thực hiện để xuất hiện. Hãy tính giá trị kỳ vọng của .
Dữ liệu vào
- Dòng đầu tiên chứa số nguyên , số bộ dữ liệu.
- dòng tiếp theo, mỗi dòng chứa một xâu chỉ gồm các ký tự '0' và '1'.
Dữ liệu ra
In ra dòng, mỗi dòng là giá trị kỳ vọng của tương ứng. Đáp án được coi là đúng nếu sai số không vượt quá .
Ràng buộc
- .
- .
Ví dụ
| Input | Output | Giải thích |
|---|---|---|
| 1 00 |
6 | Kỳ vọng số lần tung để gặp hai mặt ngửa liên tiếp là . |
| 3 0 1 01 |
2 2 4 |
Ví dụ bổ sung (không có trong đề gốc). Mỗi mặt cần trung bình lần tung; xâu 01 cần trung bình lần. |
Bình luận