← 返回题目列表

Codeforces · 1523/D

D. 爱恨交织

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

威廉正在为他的 $$$n$$$ 交易员朋友举办派对。他们开始讨论他们交易的各种货币,但有一个问题:并非他所有的交易朋友都喜欢每种货币。他们喜欢某些货币,但不喜欢其他货币。

对于 William 的每个朋友 $$$i$$$,都知道他是否喜欢货币 $$$j$$$。总共有 $$$m$$$ 种货币。众所周知,交易者可能不喜欢超过 $$$p$$$ 的货币。

因为朋友需要有一些共同的话题来讨论,所以他们需要找到基数最大(可能为空)的货币子集,这样至少有 $$$\lceil \frac{n}{2} \rceil$$$ 朋友(向上取整)喜欢这个子集中的每种货币。

输入

第一行包含三个整数$$$n、m$$$和$$$p$$$ $$$(1 \le n \le 2 \cdot 10^5, 1 \le p \le m \le 60, 1 \le p \le 15)$$$,分别是交易者好友数量、币种数量、每个好友最多可以喜欢的币种数量。

接下来的 $$$n$$$ 行包含 $$$m$$$ 个字符。如果朋友 ​​$$$i$$$ 喜欢货币 $$$j$$$,则 $$$i$$$ 第 $$$i$$$ 行的第 $$$j$$$ 字符为 $$$1$$$,否则为 $$$0$$$。保证每行的个数不超过$$$p$$$。

输出

打印一个长度为 $$$m$$$ 的字符串,它定义了最大大小的货币子集,至少有一半的朋友喜欢这些货币。属于该子集的货币必须由字符 $$$1$$$ 表示。

如果有多个答案,请打印其中一个。

示例

输入 #1

3 4 3
1000
0110
1001

输出 #1

1000

输入 #2

5 5 4
11001
10101
10010
01110
11011

输出 #2

10001

注意

在第一个示例测试用例中,只有第一种货币至少被 $$$\lceil \frac{3}{2} \rceil = 2$$$ 朋友喜欢,因此很容易证明无法找到更好的答案。

在第二个示例测试用例中,答案包括 $$$2$$$ 货币,并且会被好友 $$$1$$$、$$$2$$$ 和 $$$5$$$ 喜欢。对于这个测试用例,至少有一半的朋友喜欢其他货币,但使用它们我们无法实现更大的子集大小。