codeforces-scrape

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

988B.md (1601B)


      1 Source: https://codeforces.com/problemset/problem/988/B
      2 
      3 B. Substrings Sort
      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 $n$ strings. Each string consists of lowercase English letters. Rearrange (reorder) the given strings in such a way that for every string, all strings that are placed before it are its substrings.
     22 
     23 String $a$ is a substring of string $b$ if it is possible to choose several consecutive letters in $b$ in such a way that they form $a$. For example, string "for" is contained as a substring in strings "codeforces", "for" and "therefore", but is not contained as a substring in strings "four", "fofo" and "rof".
     24 
     25 Input
     26 
     27 The first line contains an integer $n$ ($1 \le n \le 100$) — the number of strings.
     28 
     29 The next $n$ lines contain the given strings. The number of letters in each string is from $1$ to $100$, inclusive. Each string consists of lowercase English letters.
     30 
     31 Some strings might be equal.
     32 
     33 Output
     34 
     35 If it is impossible to reorder $n$ given strings in required order, print "NO" (without quotes).
     36 
     37 Otherwise print "YES" (without quotes) and $n$ given strings in required order.
     38 
     39 Examples
     40 
     41 Input
     42 
     43 ```
     44 5  
     45 a  
     46 aba  
     47 abacaba  
     48 ba  
     49 aba
     50 ```
     51 
     52 Output
     53 
     54 ```
     55 YES  
     56 a  
     57 ba  
     58 aba  
     59 aba  
     60 abacaba
     61 ```
     62 
     63 Input
     64 
     65 ```
     66 5  
     67 a  
     68 abacaba  
     69 ba  
     70 aba  
     71 abab
     72 ```
     73 
     74 Output
     75 
     76 ```
     77 NO
     78 ```
     79 
     80 Input
     81 
     82 ```
     83 3  
     84 qwerty  
     85 qwerty  
     86 qwerty
     87 ```
     88 
     89 Output
     90 
     91 ```
     92 YES  
     93 qwerty  
     94 qwerty  
     95 qwerty
     96 ```
     97 
     98 Note
     99 
    100 In the second example you cannot reorder the strings because the string "abab" is not a substring of the string "abacaba".