codeforces-scrape

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

638B.md (2234B)


      1 Source: https://codeforces.com/problemset/problem/638/B
      2 
      3 B. Making Genome in Berland
      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 Berland scientists face a very important task - given the parts of short DNA fragments, restore the dinosaur DNA! The genome of a berland dinosaur has noting in common with the genome that we've used to: it can have 26 distinct nucleotide types, a nucleotide of each type can occur at most once. If we assign distinct English letters to all nucleotides, then the genome of a Berland dinosaur will represent a non-empty string consisting of small English letters, such that each letter occurs in it at most once.
     22 
     23 Scientists have *n* genome fragments that are represented as substrings (non-empty sequences of consecutive nucleotides) of the sought genome.
     24 
     25 You face the following problem: help scientists restore the dinosaur genome. It is guaranteed that the input is not contradictory and at least one suitable line always exists. When the scientists found out that you are a strong programmer, they asked you in addition to choose the one with the minimum length. If there are multiple such strings, choose any string.
     26 
     27 Input
     28 
     29 The first line of the input contains a positive integer *n* (1 ≤ *n* ≤ 100) — the number of genome fragments.
     30 
     31 Each of the next lines contains one descriptions of a fragment. Each fragment is a non-empty string consisting of distinct small letters of the English alphabet. It is not guaranteed that the given fragments are distinct. Fragments could arbitrarily overlap and one fragment could be a substring of another one.
     32 
     33 It is guaranteed that there is such string of distinct letters that contains all the given fragments as substrings.
     34 
     35 Output
     36 
     37 In the single line of the output print the genome of the minimum length that contains all the given parts. All the nucleotides in the genome must be distinct. If there are multiple suitable strings, print the string of the minimum length. If there also are multiple suitable strings, you can print any of them.
     38 
     39 Examples
     40 
     41 Input
     42 
     43 ```
     44 3  
     45 bcd  
     46 ab  
     47 cdef
     48 ```
     49 
     50 Output
     51 
     52 ```
     53 abcdef
     54 ```
     55 
     56 Input
     57 
     58 ```
     59 4  
     60 x  
     61 y  
     62 z  
     63 w
     64 ```
     65 
     66 Output
     67 
     68 ```
     69 xyzw
     70 ```