codeforces-scrape

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

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