codeforces-scrape

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

858D.md (1840B)


      1 Source: https://codeforces.com/problemset/problem/858/D
      2 
      3 D. Polycarp's phone book
      4 
      5 time limit per test
      6 
      7 4 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 There are *n* phone numbers in Polycarp's contacts on his phone. Each number is a 9-digit integer, starting with a digit different from 0. All the numbers are distinct.
     22 
     23 There is the latest version of Berdroid OS installed on Polycarp's phone. If some number is entered, is shows up all the numbers in the contacts for which there is a substring equal to the entered sequence of digits. For example, is there are three phone numbers in Polycarp's contacts: 123456789, 100000000 and 100123456, then:
     24 
     25 * if he enters 00 two numbers will show up: 100000000 and 100123456,
     26 * if he enters 123 two numbers will show up 123456789 and 100123456,
     27 * if he enters 01 there will be only one number 100123456.
     28 
     29 For each of the phone numbers in Polycarp's contacts, find the minimum in length sequence of digits such that if Polycarp enters this sequence, Berdroid shows this only phone number.
     30 
     31 Input
     32 
     33 The first line contains single integer *n* (1 ≤ *n* ≤ 70000) — the total number of phone contacts in Polycarp's contacts.
     34 
     35 The phone numbers follow, one in each line. Each number is a positive 9-digit integer starting with a digit from 1 to 9. All the numbers are distinct.
     36 
     37 Output
     38 
     39 Print exactly *n* lines: the *i*-th of them should contain the shortest non-empty sequence of digits, such that if Polycarp enters it, the Berdroid OS shows up only the *i*-th number from the contacts. If there are several such sequences, print any of them.
     40 
     41 Examples
     42 
     43 Input
     44 
     45 ```
     46 3  
     47 123456789  
     48 100000000  
     49 100123456
     50 ```
     51 
     52 Output
     53 
     54 ```
     55 9  
     56 000  
     57 01
     58 ```
     59 
     60 Input
     61 
     62 ```
     63 4  
     64 123456789  
     65 193456789  
     66 134567819  
     67 934567891
     68 ```
     69 
     70 Output
     71 
     72 ```
     73 2  
     74 193  
     75 81  
     76 91
     77 ```