Preparando MOJI

The minimal unique substring

1000ms 262144K

Description:

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:

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:

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.

Sample Input:

4 4

Sample Output:

1111

Sample Input:

5 3

Sample Output:

01010

Sample Input:

7 3

Sample Output:

1011011

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$$$.

Informação

Codeforces

Provedor Codeforces

Código CF1158B

Tags

constructive algorithmsmathstrings

Submetido 0

BOUA! 0

Taxa de BOUA's 0%

Datas 09/05/2023 09:47:32

Relacionados

Nada ainda