F.A.Qs Home Discuss ProblemSet Status Ranklist Contest 入门OJ LoginRegister 捐赠本站
Notice:1:注册本OJ方式请见https://www.lydsy.com/JudgeOnline/wttl/thread.php?tid=5671 2:请不要在讨论区中发空白主题帖。
Problem 4224. -- Togle

4224: Togle

Time Limit: 10 Sec  Memory Limit: 128 MBSec  Special Judge
Submit: 2  Solved: 0
[Submit][Status][Discuss]

Description

给你一个长度为n的01串,以及一个指针,初始时指针在第i0个字符上。每回合随机一个0到n-1中的数j,如果指针
之前在i上,就花费abs(i-j)的时间把指针从i移动到j上,并且把01串的第j位取反。不停这样随机,直到01串变成
全0或者全1为止,问到终止前期望花费的时间是多少?

Input

第一行两个整数,n,t,表示串长和数据组数,每组数据的串长是相等的
接下来t行,每行一个01串和一个整数,s,i0,表示初始时的串和初始位置,s的长度为n
n<=30 t<=100000 0<=i0<n

Output

t行,每行一个实数表示答案。你的答案被认为是正确的当且仅当,你与标准答案的相对误差小于1e-7

Sample Input

4 4
1000 0
0010 1
0011 2
1010 3

Sample Output

8.9375
8.5625
9.75
10.25

HINT



Source

[Submit][Status][Discuss]

HOME Back