The minimal unique substring
Contest: Codeforces Round 559 (Div. 1)
Difficulty rating: 2200
Tags: constructive algorithms, math, strings

Let $$$s$$$ be some string consisting of symbols "0" or "1". Let's call a string $$$t$$$ a substring of string $$$s$$$, if there exists such number $$$1 \leq l \leq |s| - |t| + 1$$$ that $$$t = s_l s_{l+1} \ldots s_{l + |t| - 1}$$$. Let's call a substring $$$t$$$ of string $$$s$$$ unique, if there exist only one such $$$l$$$.

For example, let $$$s = $$$"1010111". A string $$$t = $$$"010" is an unique substring of $$$s$$$, because $$$l = 2$$$ is the only one suitable number. But, for example $$$t = $$$"10" isn't a unique substring of $$$s$$$, because $$$l = 1$$$ and $$$l = 3$$$ are suitable. And for example $$$t =$$$"00" at all isn't a substring of $$$s$$$, because there is no suitable $$$l$$$.

Today Vasya solved the following problem at the informatics lesson: given a string consisting of symbols "0" and "1", the task is to find the length of its minimal unique substring. He has written a solution to this problem and wants to test it. He is asking you to help him.

You are given $$$2$$$ positive integers $$$n$$$ and $$$k$$$, such that $$$(n \bmod 2) = (k \bmod 2)$$$, where $$$(x \bmod 2)$$$ is operation of taking remainder of $$$x$$$ by dividing on $$$2$$$. Find any string $$$s$$$ consisting of $$$n$$$ symbols "0" or "1", such that the length of its minimal unique substring is equal to $$$k$$$.

Input format:
The first line contains two integers $$$n$$$ and $$$k$$$, separated by spaces ($$$1 \leq k \leq n \leq 100\,000$$$, $$$(k \bmod 2) = (n \bmod 2)$$$).

Output format:
Print a string $$$s$$$ of length $$$n$$$, consisting of symbols "0" and "1". Minimal length of the unique substring of $$$s$$$ should be equal to $$$k$$$. You can find any suitable string. It is guaranteed, that there exists at least one such string.

Constraints:
Time limit: 1.0 s
Memory limit: 256.0 MB

Note:
In the first test, it's easy to see, that the only unique substring of string $$$s = $$$"1111" is all string $$$s$$$, which has length $$$4$$$.

In the second test a string $$$s = $$$"01010" has minimal unique substring $$$t =$$$"101", which has length $$$3$$$.

In the third test a string $$$s = $$$"1011011" has minimal unique substring $$$t =$$$"110", which has length $$$3$$$.

Example input:
4 4

Example output:
1111

Example input:
5 3

Example output:
01010

Editorial:
Let's define the value $$$a = \frac {n-k} 2$$$. We know, that $$$(k \bmod 2) = (n \bmod 2)$$$ so $$$a$$$ is integer number. Let's construct this string $$$s$$$: $$$a$$$ symbols "0", $$$1$$$ symbol "1", $$$a$$$ symbols "0", $$$1$$$ symbol "1", $$$\ldots$$$ Let's prove, that this string satisfy the conditions. Let's note, that it's period is equal to $$$(a+1)$$$.
Let the substring $$$t$$$ be unique. Let's look at the only $$$l$$$ for this substring. But if $$$l > a + 1$$$, then $$$l - (a + 1)$$$ satisfy (as the left border of the string $$$t$$$ occurrence), if $$$l \leq n - (a + |t|)$$$ then $$$l + (a + 1)$$$ satisfy (because the period of $$$s$$$ is equal to $$$(a + 1)$$$, so shift on $$$(a + 1)$$$ don't change anything). So $$$l \leq a + 1$$$ and $$$n - (a + |t|) < l$$$, because in other case $$$l$$$ can't be the only. So $$$n - (a + |t|) < l \leq a + 1$$$ so $$$n - (a + |t|) < a + 1$$$ so $$$n - (a + |t|) \leq a$$$ so $$$n - 2 \cdot a \leq |t|$$$ so $$$k \leq |t|$$$.
As the example of the unique substring of length $$$k$$$ we can take $$$t = s_{a+1} \ldots s_{n-a}$$$.
Complexity: $$$O(n)$$$.
Bonus: How to solve the problem without condition, that $$$(k \bmod 2) = (n \bmod 2)$$$? For what $$$k$$$ the answer exists?