306178: CF1158B. The minimal unique substring

Memory Limit:256 MB Time Limit:1 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

The minimal unique substring

题意翻译

构造一个长度为$n$的$01$串$s$,使得: - 任意长度小于$k$的$01$串,或者不是$s$的子串,或者在$s$中出现了至少$2$次 - 至少存在一个长度为$k$的$01$串,在$s$中出现了恰好一次 保证$n\equiv k (mod 2)$

题目描述

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

输入输出格式

输入格式


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

输出格式


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.

输入输出样例

输入样例 #1

4 4

输出样例 #1

1111

输入样例 #2

5 3

输出样例 #2

01010

输入样例 #3

7 3

输出样例 #3

1011011

说明

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

Input

题意翻译

构造一个长度为$n$的$01$串$s$,使得: - 任意长度小于$k$的$01$串,或者不是$s$的子串,或者在$s$中出现了至少$2$次 - 至少存在一个长度为$k$的$01$串,在$s$中出现了恰好一次 保证$n\equiv k (mod 2)$

加入题单

上一题 下一题 算法标签: