2250B.md (2017B)
1 Source: https://codeforces.com/problemset/problem/2250/B 2 3 B. String Construction 4 5 time limit per test 6 7 1 second 8 9 memory limit per test 10 11 256 megabytes 12 13 input 14 15 standard input 16 17 output 18 19 standard output 20 21 You are given two integers $n$ and $k$. 22 23 Construct a binary string$^{\text{∗}}$ $s$ of length $n$, such that both of the following conditions hold: 24 25 * The absolute difference between the number of characters $\mathtt{0}$ and the number of characters $\mathtt{1}$ in $s$ is at most $1$. 26 * There are exactly $k$ pairs of adjacent equal characters in $s$. Formally, there are exactly $k$ indices $i$ ($1 \le i \le n-1$) satisfying $s_i = s_{i + 1}$. 27 28 Or determine that no such string exists. 29 30 $^{\text{∗}}$A binary string is a string where each character is either $\mathtt{0}$ or $\mathtt{1}$. 31 32 Input 33 34 Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 1000$). The description of the test cases follows. 35 36 The only line of each test case contains two integers $n$ and $k$ ($2 \le n \le 2 \cdot 10^5$, $0 \le k \le n-1$). 37 38 It is guaranteed that the sum of $n$ over all test cases does not exceed $2 \cdot 10^5$. 39 40 Output 41 42 For each test case, output a binary string $s$ of length $n$ — the string you constructed. Print $-1$ if such a string does not exist. 43 44 If there are multiple answers, you may output any of them. 45 46 Example 47 48 Input 49 50 ``` 51 8 52 53 5 2 54 55 4 3 56 57 6 1 58 59 5 0 60 61 7 3 62 63 4 2 64 65 3 2 66 67 7 4 68 ``` 69 70 Output 71 72 ``` 73 01110 74 75 -1 76 77 101001 78 79 01010 80 81 0100011 82 83 0011 84 85 -1 86 87 0111000 88 ``` 89 90 Note 91 92 In the first test case, one possible answer is $s=\mathtt{01110}$. It contains three characters $\mathtt{1}$ and two characters $\mathtt{0}$, and there are exactly $2$ adjacent equal pairs in $s$: $(s_2, s_3)$ and $(s_3, s_4)$. 93 94 In the second test case, $k=n-1$. All characters in $s$ should be equal, so the numbers of characters $\mathtt{0}$ and $\mathtt{1}$ could not differ by at most $1$. Thus, the answer is $-1$. 95 96 In the third test case, note that $\mathtt{010110}$ is also a possible answer.