← 返回题目列表

AtCoder · agc024_f

F. 简单子序列问题

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

分数: 2300 点

问题陈述

给你一套 S 的字符串组成 0 和 1,和一个整数 K.

找到最长的字符串,它是 K 或更多不同的字符串 S。 如果有多个字符串满足该条件,则找到按字典顺序最小的该字符串。

在这里, S 按以下格式给出:

  • 直接给你的数据是一个整数 N,和 N+1 字符串 X_0,X_1,...,X_N。对于每一个 i (0\leq i\leq N)的长度 X_i is 2^i.
  • 对于每对两个整数 (i,j) (0\leq i\leq N,0\leq j\leq 2^i-1), j- 第一个字符 X_i is 1 当且仅当二进制表示 j 与 i 数字(可能带有前导零)属于 S。这里,第一个和最后一个字符 X_i 被称为 分别是 0-th 和 (2^i-1)个字符。
  • S 不包含长度为的字符串 N+1 或更多。

这里是一个字符串 A 是另一个字符串的子序列 B 当存在整数序列时 t_1 < ... < t_{|A|} 这样,对于每个 i (1\leq i\leq |A|), i- 第一个字符 A 和 t_i- 第一个字符 B 相等。

约束

  • 0 \leq N \leq 20
  • X_i(0\leq i\leq N) 是一个长度为 2^i 组成 0 和 1.
  • 1 \leq K \leq |S|
  • K 是一个整数。

输入

输入由标准输入按以下格式给出:

N K
X_0
:
X_N

输出

打印最长字符串中按字典顺序最小的字符串,这些字符串是 K 或更多不同的字符串 S.


示例输入 1

3 4
1
01
1011
01001110

示例输出 1

10

以下字符串属于 S:空字符串, 1, 00, 10, 11, 001, 100, 101 和 110。 最长字符串(四个或更多字符串的子序列)中按字典顺序排列的最小字符串是 10.


示例输入 2

4 6
1
01
1011
10111010
1101110011111101

示例输出 2

100

示例输入 3

2 5
0
11
1111

示例输出 3


答案是空字符串。