← 返回题目列表

Codeforces · 1158/B

B. 最小唯一子串

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

设 $$$s$$$ 是由符号“0”或“1”组成的字符串。我们称字符串 $$$t$$$ 为字符串 $$$s$$$ 的子字符串,如果存在这样的数字 $$$1 \leq l \leq |s| -|t| + 1$$$ 即 $$$t = s_l s_{l+1} \ldots s_{l + |t| - 1}$$$。如果只存在一个这样的 $$$l$$$,我们称字符串 $$$s$$$ 的子字符串 $$$t$$$ 为唯一。

例如,令 $$$s = $$$"1010111"。字符串 $$$t = $$$"010" 是 $$$s$$$ 的唯一子字符串,因为 $$$l = 2$$$ 是唯一一个合适的数字。但是,例如 $$$t = $$$"10" 不是 $$$s$$$ 的唯一子字符串,因为 $$$l = 1$$$ 和 $$$l = 3$$$ 是合适的。例如 $$$t =$$$"00" 根本不是 $$$s$$$ 的子字符串,因为没有合适的 $$$l$$$。

今天 Vasya 在信息学课上解决了以下问题:给定一个由符号“0”和“1”组成的字符串,任务是找到其最小唯一子串的长度。他已经编写了这个问题的解决方案并想对其进行测试。他请求你帮助他。

给定 $$$2$$$ 正整数 $$$n$$$ 和 $$$k$$$,使得 $$$(n \bmod 2) = (k \bmod 2)$$$,其中 $$$(x \bmod 2)$$$ 是除以 $$$2$$$ 取 $$$x$$$ 余数的运算。找到由$$$n$$$符号“0”或“1”组成的任意字符串$$$s$$$,使得其最小唯一子串的长度等于$$$k$$$。

输入

第一行包含两个整数 $$$n$$$ 和 $$$k$$$,用空格分隔 ($$$1 \leq k \leq n \leq 100\,000$$$, $$$(k \bmod 2) = (n \bmod 2)$$$)。

输出

打印长度为$$$n$$$的字符串$$$s$$$,由符号“0”和“1”组成。 $$$s$$$ 的唯一子字符串的最小长度应等于 $$$k$$$。您可以找到任何合适的字符串。保证至少存在一个这样的字符串。

示例

输入 #1

4 4

输出 #1

1111

输入 #2

5 3

输出 #2

01010

输入 #3

7 3

输出 #3

1011011

注意

在第一个测试中,很容易看出,字符串 $$$s = $$$"1111" 的唯一唯一子字符串是所有字符串 $$$s$$$,其长度为 $$$4$$$。

在第二个测试中,字符串 $$$s = $$$"01010" 具有最小唯一子字符串 $$$t =$$$"101",其长度为 $$$3$$$。

在第三个测试中,字符串 $$$s = $$$"1011011" 具有最小的唯一子字符串 $$$t =$$$"110",其长度为 $$$3$$$。