codeforces-scrape

Codeforces scraped problems and editorials
git clone git://git.laack.co/codeforces-scrape.git
Log | Files | Refs | README

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.