题目描述

我有一个长度为 $N$ 的二进制数字序列。我正在寻找一个子串，使得其中 $1$ 的比例恰好等于给定的分数 $F$，但这样的子串可能不存在，所以我会选择一个比例最接近 $F$ 的子串。

你能找到一个子串，使得其中 $1$ 的比例尽可能接近给定的分数 $F$ 吗？请输出这样一个子串最早出现的起始下标。

输入格式

输入的第一行为测试用例数 $T$。接下来有 $T$ 组测试数据。每组测试数据的第一行为 $N$ 和 $F$。$F$ 是一个介于 $0$ 和 $1$ 之间的十进制小数，且小数点后恰好有 $6$ 位。下一行为 $N$ 个数字，每个数字为 $0$ 或 $1$。

输出格式

对于每组测试数据，输出一行，格式为 "Case #x: y"，其中 $x$ 表示测试用例编号（从 $1$ 开始），$y$ 表示满足条件的子串的最小起始下标（从 $0$ 开始）。如果有多个答案，输出最小的下标。

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

提示

样例解释

在第 1 组测试数据中，没有子串的 $1$ 比例恰好等于 $666667/1000000$。最接近的比例是 $2/3$。输入字符串中有 $5$ 个子串达到了这个比例——长度为 $3$ 的子串有 $3$ 个，分别从下标 $5, 7, 8$ 开始（$101, 101, 011$）；长度为 $6$ 的子串有 $2$ 个，分别从下标 $5, 6$ 开始（$101011, 010111$）。这些下标中最小的是 $5$。

数据范围

• $1 \leq T \leq 100$。
• $0 \leq F \leq 1$。
• $F$ 恰好有 $6$ 位小数。

小数据范围

• 时间限制：5 秒。
• $1 \leq N \leq 1000$。

大数据范围

• 时间限制：10 秒。
• $1 \leq N \leq 500,\!000$。

由 ChatGPT 4.1 翻译