시간 제한메모리 제한제출정답맞힌 사람정답 비율
5 초 512 MB23191780.952%

문제

I have a sequence of 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 F? Output the earliest possible index at which such a substring starts.

입력

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

Limits

  • 1 ≤ T ≤ 100.
  • 0 ≤ F ≤ 1
  • F will have exactly 6 digits after the decimal point.
  • 1 ≤ N ≤ 500,000.

출력

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

예제 입력 1

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

예제 출력 1

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

힌트

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.

채점 및 기타 정보

  • 예제는 채점하지 않는다.