← 返回题目列表

Codeforces · 1884/B

B. 鬼屋

中文机器翻译题面 查看原题

给你一个二进制表示的数字,由 $$$n$$$ 位组成,可能带有前导零。例如,对于 $$$n = 5$$$,数字 $$$6$$$ 将指定为 $$$00110$$$,而对于 $$$n = 4$$$,数字 $$$9$$$ 将指定为 $$$1001$$$。

让我们修复一些整数$$$i$$$,使得$$$1 \le i \le n$$$。在一次操作中,您可以交换二进制表示中的任意两个相邻位。您的目标是找到使该数字能被 $$$2^i$$$ 整除所需执行的最少运算次数,或者说这是不可能的。

请注意,对于每个 $$$1 \le i \le n$$$ 您正在独立解决问题。

输入

每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 10^4$$$)。测试用例的描述如下。

每个测试用例的第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 10^5$$$) - 数字的二进制表示形式的长度。

每个测试用例的第二行包含一个长度为 $$$n$$$ 的字符串,由 $$$0$$$ 和 $$$1$$$ 组成,—数字的二进制表示形式。

保证所有测试用例的 $$$n$$$ 总和不超过 $$$2 \cdot 10^5$$$。

输出

对于每个测试用例,对于每个 $$$1 \le i \le n$$$ 输出使该数字可被 $$$2^i$$$ 整除所需的最小操作数,如果不可能,则输出 $$$-1$$$。

示例

输入 #1

6
1
1
2
01
3
010
5
10101
7
0000111
12
001011000110

输出 #1

-1 
1 -1 
0 1 -1 
1 3 -1 -1 -1 
3 6 9 12 -1 -1 -1 
0 2 4 6 10 15 20 -1 -1 -1 -1 -1

注意

在第一个测试用例中,我们无法交换任何元素,并且数字 $$$1$$$ 不能被 $$$2$$$ 整除。

在第二个测试用例中,初始编号为$$$1$$$。它不能被$$$2$$$整除,但如果我们进行运算,则得到二进制表示的数$$$10$$$,它等于十进制表示的$$$2$$$,因此它可以被$$$2$$$整除。但这个数字不能被 $$$4$$$ 整除,并且我们无法使用该操作获得任何其他数字。

在第三个测试用例中,初始数字是$$$2$$$。对于$$$i = 1$$$,我们不必执行任何操作,因为初始数字可以被$$$2$$$整除。对于$$$i = 2$$$,我们可以执行一个交换前两位的操作(我们将获得二进制表示的$$$100$$$,对应于数字$$$4$$$)。 $$$i = 3$$$ 没有答案。