1342B.md (1877B)
1 Source: https://codeforces.com/problemset/problem/1342/B 2 3 B. Binary Period 4 5 time limit per test 6 7 2 seconds 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 Let's say string $s$ has period $k$ if $s_i = s_{i + k}$ for all $i$ from $1$ to $|s| - k$ ($|s|$ means length of string $s$) and $k$ is the minimum positive integer with this property. 22 23 Some examples of a period: for $s$="0101" the period is $k=2$, for $s$="0000" the period is $k=1$, for $s$="010" the period is $k=2$, for $s$="0011" the period is $k=4$. 24 25 You are given string $t$ consisting only of 0's and 1's and you need to find such string $s$ that: 26 27 1. String $s$ consists only of 0's and 1's; 28 2. The length of $s$ doesn't exceed $2 \cdot |t|$; 29 3. String $t$ is a subsequence of string $s$; 30 4. String $s$ has smallest possible period among all strings that meet conditions 1—3. 31 32 Let us recall that $t$ is a subsequence of $s$ if $t$ can be derived from $s$ by deleting zero or more elements (any) without changing the order of the remaining elements. For example, $t$="011" is a subsequence of $s$="10101". 33 34 Input 35 36 The first line contains single integer $T$ ($1 \le T \le 100$) — the number of test cases. 37 38 Next $T$ lines contain test cases — one per line. Each line contains string $t$ ($1 \le |t| \le 100$) consisting only of 0's and 1's. 39 40 Output 41 42 Print one string for each test case — string $s$ you needed to find. If there are multiple solutions print any one of them. 43 44 Example 45 46 Input 47 48 ``` 49 4 50 00 51 01 52 111 53 110 54 ``` 55 56 Output 57 58 ``` 59 00 60 01 61 11111 62 1010 63 ``` 64 65 Note 66 67 In the first and second test cases, $s = t$ since it's already one of the optimal solutions. Answers have periods equal to $1$ and $2$, respectively. 68 69 In the third test case, there are shorter optimal solutions, but it's okay since we don't need to minimize the string $s$. String $s$ has period equal to $1$.