codeforces-scrape

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

510C.md (2460B)


      1 Source: https://codeforces.com/problemset/problem/510/C
      2 
      3 C. Fox And Names
      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 stdin
     16 
     17 output
     18 
     19 stdout
     20 
     21 Fox Ciel is going to publish a paper on FOCS (Foxes Operated Computer Systems, pronounce: "Fox"). She heard a rumor: the authors list on the paper is always sorted in the lexicographical order.
     22 
     23 After checking some examples, she found out that sometimes it wasn't true. On some papers authors' names weren't sorted in lexicographical order in normal sense. But it was always true that after some modification of the order of letters in alphabet, the order of authors becomes lexicographical!
     24 
     25 She wants to know, if there exists an order of letters in Latin alphabet such that the names on the paper she is submitting are following in the lexicographical order. If so, you should find out any such order.
     26 
     27 Lexicographical order is defined in following way. When we compare *s* and *t*, first we find the leftmost position with differing characters: *s**i* ≠ *t**i*. If there is no such position (i. e. *s* is a prefix of *t* or vice versa) the shortest string is less. Otherwise, we compare characters *s**i* and *t**i* according to their order in alphabet.
     28 
     29 Input
     30 
     31 The first line contains an integer *n* (1 ≤ *n* ≤ 100): number of names.
     32 
     33 Each of the following *n* lines contain one string *name**i* (1 ≤ |*name**i*| ≤ 100), the *i*-th name. Each name contains only lowercase Latin letters. All names are different.
     34 
     35 Output
     36 
     37 If there exists such order of letters that the given names are sorted lexicographically, output any such order as a permutation of characters 'a'–'z' (i. e. first output the first letter of the modified alphabet, then the second, and so on).
     38 
     39 Otherwise output a single word "Impossible" (without quotes).
     40 
     41 Examples
     42 
     43 Input
     44 
     45 ```
     46 3  
     47 rivest  
     48 shamir  
     49 adleman
     50 ```
     51 
     52 Output
     53 
     54 ```
     55 bcdefghijklmnopqrsatuvwxyz
     56 ```
     57 
     58 Input
     59 
     60 ```
     61 10  
     62 tourist  
     63 petr  
     64 wjmzbmr  
     65 yeputons  
     66 vepifanov  
     67 scottwu  
     68 oooooooooooooooo  
     69 subscriber  
     70 rowdark  
     71 tankengineer
     72 ```
     73 
     74 Output
     75 
     76 ```
     77 Impossible
     78 ```
     79 
     80 Input
     81 
     82 ```
     83 10  
     84 petr  
     85 egor  
     86 endagorion  
     87 feferivan  
     88 ilovetanyaromanova  
     89 kostka  
     90 dmitriyh  
     91 maratsnowbear  
     92 bredorjaguarturnik  
     93 cgyforever
     94 ```
     95 
     96 Output
     97 
     98 ```
     99 aghjlnopefikdmbcqrstuvwxyz
    100 ```
    101 
    102 Input
    103 
    104 ```
    105 7  
    106 car  
    107 care  
    108 careful  
    109 carefully  
    110 becarefuldontforgetsomething  
    111 otherwiseyouwillbehacked  
    112 goodluck
    113 ```
    114 
    115 Output
    116 
    117 ```
    118 acbdefhijklmnogpqrstuvwxyz
    119 ```