题目描述

I have a sequence of $\mathbf{N}$ binary digits. I am looking for a substring with just the right proportion of 0s and 1s, but it may not exist, so I will settle for something that's just pretty good.

Can you find a substring where the fraction of 1s is as close as possible to the given fraction $\mathbf{F}$? Output the earliest possible index at which such a substring starts.

输入格式

The first line of the input gives the number of test cases, $\mathbf{T}$. $\mathbf{T}$ test cases follow. Each one starts with a line containing $\mathbf{N}$ and $\mathbf{F}$. $\mathbf{F}$ will be a decimal fraction between 0 and 1 inclusive, with exactly 6 digits after the decimal point. The next line contains $\mathbf{N}$ digits, each being either 0 or 1.

输出格式

For each test case, output one line containing "Case #x: y", where $\mathrm{x}$ is the test case number (starting from 1) and $\mathrm{y}$ is the 0-based index of the start of the substring with the fraction of 1s that is as close as possible to $\mathbf{F}$. If there are multiple possible answers, output the smallest correct value.

5
12 0.666667
001001010111
11 0.400000
10000100011
9 0.000000
111110111
5 1.000000
00000
15 0.333333
000000000011000

Case #1: 5
Case #2: 5
Case #3: 5
Case #4: 0
Case #5: 6

提示

Sample Explanation

In Case #1, there is no substring that has exactly a $1$-proportion of exactly $666667/1000000$. The closest we can get is $2/3$. The input string has 5 substrings that achieve it -- $3$ substrings of length 3 that start at indices $5, 7,$ and $8$ ($101, 101,$ and $011$); as well as two substrings of length $6$ that start at indices $5$ and $6$ ($101011$ and $010111$). The smallest of these indices is $5$.

Limits

• $1 \leq \mathbf{T} \leq 100$.
• $0 \leq \mathbf{F} \leq 1$
• $\mathbf{F}$ will have exactly 6 digits after the decimal point.

Small dataset

• Time limit: 240 5 seconds.
• $1 \leq \mathbf{N} \leq 1000$.

Large dataset

• Time limit: 480 10 seconds.
• $1 \leq \mathbf{N} \leq 500,000$.