codeforces-scrape

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

1537E1.md (1969B)


      1 Source: https://codeforces.com/problemset/problem/1537/E1
      2 
      3 E1. Erase and Extend (Easy Version)
      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 This is the easy version of the problem. The only difference is the constraints on $n$ and $k$. You can make hacks only if all versions of the problem are solved.
     22 
     23 You have a string $s$, and you can do two types of operations on it:
     24 
     25 * Delete the last character of the string.
     26 * Duplicate the string: $s:=s+s$, where $+$ denotes concatenation.
     27 
     28 You can use each operation any number of times (possibly none).
     29 
     30 Your task is to find the lexicographically smallest string of length exactly $k$ that can be obtained by doing these operations on string $s$.
     31 
     32 A string $a$ is lexicographically smaller than a string $b$ if and only if one of the following holds:
     33 
     34 * $a$ is a prefix of $b$, but $a\ne b$;
     35 * In the first position where $a$ and $b$ differ, the string $a$ has a letter that appears earlier in the alphabet than the corresponding letter in $b$.
     36 
     37 Input
     38 
     39 The first line contains two integers $n$, $k$ ($1 \leq n, k \leq 5000$) — the length of the original string $s$ and the length of the desired string.
     40 
     41 The second line contains the string $s$, consisting of $n$ lowercase English letters.
     42 
     43 Output
     44 
     45 Print the lexicographically smallest string of length $k$ that can be obtained by doing the operations on string $s$.
     46 
     47 Examples
     48 
     49 Input
     50 
     51 ```
     52 8 16
     53 dbcadabc
     54 ```
     55 
     56 Output
     57 
     58 ```
     59 dbcadabcdbcadabc
     60 ```
     61 
     62 Input
     63 
     64 ```
     65 4 5
     66 abcd
     67 ```
     68 
     69 Output
     70 
     71 ```
     72 aaaaa
     73 ```
     74 
     75 Note
     76 
     77 In the first test, it is optimal to make one duplication: "dbcadabc" $\to$ "dbcadabcdbcadabc".
     78 
     79 In the second test it is optimal to delete the last $3$ characters, then duplicate the string $3$ times, then delete the last $3$ characters to make the string have length $k$.
     80 
     81 "abcd" $\to$ "abc" $\to$ "ab" $\to$ "a" $\to$ "aa" $\to$ "aaaa" $\to$ "aaaaaaaa" $\to$ "aaaaaaa" $\to$ "aaaaaa" $\to$ "aaaaa".