trang chủ / đề bài / icpc21_mb_c

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 S, ta tung đồng xu liên tục cho đến khi S xuất hiện trong dãy kết quả thì dừng lại.

Gọi T là số lần tung đồng xu cần thực hiện để S xuất hiện. Hãy tính giá trị kỳ vọng của T.

Dữ liệu vào

  • Dòng đầu tiên chứa số nguyên Q, số bộ dữ liệu.
  • Q dòng tiếp theo, mỗi dòng chứa một xâu S chỉ gồm các ký tự '0' và '1'.

Dữ liệu ra

In ra Q dòng, mỗi dòng là giá trị kỳ vọng của T tương ứng. Đáp án được coi là đúng nếu sai số không vượt quá 10−9.

Ràng buộc

  • 1≤Q≤104.
  • 1≤|S|≤20.

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à 6.
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 2 lần tung; xâu 01 cần trung bình 4 lần.

Bình luận

Không có bình luận tại thời điểm này.

gnatmake 12.2.0 a68g 3.1.2 nasm 2.16.1 as_x64 2.47 awk 1.3.4 gcc 16.2.0 dotnet 10.0.402 g++ 16.2.0 g++-themis 16.2.0 g++17 16.2.0 g++20 16.2.0 g++23 16.2.0 clang++ 22.1.8 dmd 2.113.0 dart 3.13.6 gforth 0.7.3 gfortran 15.3.0 go 1.27.3 groovyc 5.1.3 javac 26.0.2.1 node 26.12.1 julia 1.13.2 kotlinc 2.4.21 lean 4.35.0 sbcl 2.2.9 lua 5.5.1 nim 2.2.12 fpc 3.2.2 fpc-themis 3.2.2 perl 5.42.3 php 8.5.12 pike 8.0 swipl 9.0.4 pypy3 7.3.23 python3 3.15.1 racket 8.7 ruby 4.0.8 rustc 1.99.1 csc 5.3.0 ctoj-scratch 0.0.1 sed 4.9 swiftc 6.4.1 tclsh 8.6 bun 1.4.4 deno 2.9.8 v 0.5.2 zig 0.17.0