← 返回题目列表

Codeforces · 1360/H

H. 二进制中位数

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

考虑长度为 $$$m$$$ ($$$1 \le m \le 60$$$) 的所有二进制字符串。二进制字符串是仅由字符 0 和 1 组成的字符串。例如,0110是二进制字符串,而012aba则不是。显然,这样的字符串总共有 $$$2^m$$$ 个。

字符串 $$$s$$$ 按字典顺序小于字符串 $$$t$$$(两者的长度 $$$m$$$ 相同),如果在它们不同的左边第一个位置 $$$i$$$,我们有 $$$s[i] < t[i]$$$。这正是在字典和大多数现代编程语言中以标准方式比较字符串时的比较方式。例如,字符串 01011 按字典顺序小于字符串 01100,因为前两个字符相同,并且第一个字符串中的第三个字符小于第二个字符串中的第三个字符。

我们从这个集合中删除 $$$n$$$ ($$$1 \le n \le \min(2^m-1, 100)$$$) 不同的二进制字符串 $$$a_1, a_2, \ldots, a_n$$$,每个长度为 $$$m$$$。因此,该集合将具有 $$$k=2^m-n$$$ 字符串。按字典升序对结果集中的所有字符串进行排序(如字典中一样)。

我们对排序后的所有字符串进行编号,从 $$$0$$$ 到 $$$k-1$$$。打印索引为 $$$\lfloor \frac{k-1}{2} \rfloor$$$ 的字符串(这样的元素称为中位数),其中 $$$\lfloor x \rfloor$$$ 是将数字向下舍入到最接近的整数。

例如,如果 $$$n=3$$$、$$$m=3$$$ 和 $$$a=[$$$010, 111, 001$$$]$$$,则删除字符串 $$$a_i$$$ 并排序后,结果将采用以下形式:$$$[$$$000, 011, 100, 101, 110$$$]$$$。因此,所需的中位数是 100。

输入

第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 1000$$$) — 测试用例的数量。然后,$$$t$$$ 测试用例如下。

每个测试用例的第一行包含整数 $$$n$$$ ($$$1 \le n \le \min(2^m-1, 100)$$$) 和 $$$m$$$ ($$$1 \le m \le 60$$$),其中 $$$n$$$ 是要删除的字符串数量,$$$m$$$ 是二进制字符串的长度。接下来的 $$$n$$$ 行包含 $$$a_1、a_2、\ldots、a_n$$$ — 长度为 $$$m$$$ 的不同二进制字符串。

一次测试中所有测试用例中所有给定二进制字符串的总长度不超过$$$10^5$$$。

输出

打印测试用例的 $$$t$$$ 答案。对于每个测试用例,打印一个长度为 $$$m$$$ 的字符串 - 相应测试用例中剩余字符串的排序序列的中位数。

示例

输入 #1

5
3 3
010
001
111
4 3
000
111
100
011
1 1
1
1 1
0
3 2
00
01
10

输出 #1

100
010
0
1
11

注意

第一个测试用例在语句中进行了解释。

在第二个测试用例中,删除字符串并排序后的结果是$$$[$$$001, 010, 101, 110$$$]$$$。因此,所需的中位数是 010。