分数: 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
答案是空字符串。