codeforces-scrape

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

278B.md (2279B)


      1 Source: https://codeforces.com/problemset/problem/278/B
      2 
      3 B. New Problem
      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 Coming up with a new problem isn't as easy as many people think. Sometimes it is hard enough to name it. We'll consider a title original if it doesn't occur as a substring in any titles of recent Codeforces problems.
     22 
     23 You've got the titles of *n* last problems — the strings, consisting of lowercase English letters. Your task is to find the shortest original title for the new problem. If there are multiple such titles, choose the lexicographically minimum one. Note, that title of the problem can't be an empty string.
     24 
     25 A substring *s*[*l*... *r*] (1 ≤ *l* ≤ *r* ≤ |*s*|) of string *s* = *s*1*s*2... *s*|*s*| (where |*s*| is the length of string *s*) is string *s**l**s**l* + 1... *s**r*.
     26 
     27 String *x* = *x*1*x*2... *x**p* is lexicographically smaller than string *y* = *y*1*y*2... *y**q*, if either *p* < *q* and *x*1 = *y*1, *x*2 = *y*2, ... , *x**p* = *y**p*, or there exists such number *r* (*r* < *p*, *r* < *q*), that *x*1 = *y*1, *x*2 = *y*2, ... , *x**r* = *y**r* and *x**r* + 1 < *y**r* + 1. The string characters are compared by their ASCII codes.
     28 
     29 Input
     30 
     31 The first line contains integer *n* (1 ≤ *n* ≤ 30) — the number of titles you've got to consider. Then follow *n* problem titles, one per line. Each title only consists of lowercase English letters (specifically, it doesn't contain any spaces) and has the length from 1 to 20, inclusive.
     32 
     33 Output
     34 
     35 Print a string, consisting of lowercase English letters — the lexicographically minimum shortest original title.
     36 
     37 Examples
     38 
     39 Input
     40 
     41 ```
     42 5  
     43 threehorses  
     44 goodsubstrings  
     45 secret  
     46 primematrix  
     47 beautifulyear
     48 ```
     49 
     50 Output
     51 
     52 ```
     53 j
     54 ```
     55 
     56 Input
     57 
     58 ```
     59 4  
     60 aa  
     61 bdefghijklmn  
     62 opqrstuvwxyz  
     63 c
     64 ```
     65 
     66 Output
     67 
     68 ```
     69 ab
     70 ```
     71 
     72 Note
     73 
     74 In the first sample the first 9 letters of the English alphabet (a, b, c, d, e, f, g, h, i) occur in the problem titles, so the answer is letter j.
     75 
     76 In the second sample the titles contain 26 English letters, so the shortest original title cannot have length 1. Title aa occurs as a substring in the first title.