codeforces-scrape

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

2181A.md (3164B)


      1 Source: https://codeforces.com/problemset/problem/2181/A
      2 
      3 A. Alphabet City
      4 
      5 time limit per test
      6 
      7 3 seconds
      8 
      9 memory limit per test
     10 
     11 1024 megabytes
     12 
     13 input
     14 
     15 standard input
     16 
     17 output
     18 
     19 standard output
     20 
     21 Al is an urban designer in Alphabet City, and today their task is to prepare signs for $n$ city streets. In Alphabet City, the street signs simply consist of the street names composed of capital identically stamped English metal letters. For instance, if, during nighttime, someone sneakily exchanges the first letters on NERC street and on NEF street, the next day nobody will see the difference as the letter 'N' is identical on both signs.
     22 
     23 Al is planning to put $m$ signs on each street, and they have already ordered the required number of brass letters for each of the street names from the metallurgical plant. However, one hour before the order arrived, Al got a call from the plant's manager with a devastating piece of news: they lost one of the items from the list of street names! To mitigate the issue, Al decided for now to put as many signs as possible on each street whose order was not lost, and, with the leftover letters, to prepare at least one sign for the street whose order was lost.
     24 
     25 Formally, if $s_1, \ldots, s_n$ are the street names, and $\ell$ is the index of the missing item from the order, Al is interested in the maximum integer $k$ such that it is possible, from all the letters of $m$ copies of $s_1, \ldots, s_{\ell - 1}, s_{\ell + 1}, \ldots, s_n$, to compose $k$ copies of $s_1, \ldots, s_{\ell - 1}, s_{\ell + 1}, \ldots, s_n$ and additionally at least one copy of $s_\ell$, or to determine that such a composition is impossible for any non-negative $k$.
     26 
     27 Al still does not know which of the items was lost. Write a program that, given $m$ and all street names, for each $\ell \in \{1, 2, \ldots, n\}$ prints the maximum value of $k$, or $-1$ if such a composition is impossible.
     28 
     29 Input
     30 
     31 The first line consists of two integers $n$ and $m$, denoting the number of streets in Alphabet City for which the signs are needed and the number of copies of each street name that Al initially ordered ($2 \le n \le 2 \cdot 10^5$; $1 \le m \le 5 \cdot 10^5$). Each of the next $n$ lines consists of one string $s_i$ — the street name ($1 \le \left|s_i\right| \le 5 \cdot 10^5$). All these names are composed of capital English letters. Some or all of these names may coincide. It is guaranteed that the sum of the lengths of all the street names does not exceed $5 \cdot 10^5$.
     32 
     33 Output
     34 
     35 Print $n$ integers, the $\ell$-th of them denoting the maximum integer $k$ such that the letters of $m \times s_1$, ..., $m \times s_{\ell - 1}$, $m \times s_{\ell + 1}$, ..., $m \times s_n$ (where $m \times s$ denotes $m$ copies of street name $s$) are enough to compose $k \times s_1$, ..., $k \times s_{\ell - 1}$, $1 \times s_\ell$, $k \times s_{\ell + 1}$, ..., $k \times s_n$. If, for the given value of $\ell$, these letters are insufficient for any integer $k \ge 0$, print $-1$ instead.
     36 
     37 Examples
     38 
     39 Input
     40 
     41 ```
     42 3 10
     43 
     44 NEERC
     45 
     46 NERC
     47 
     48 NEF
     49 ```
     50 
     51 Output
     52 
     53 ```
     54 9 9 -1
     55 ```
     56 
     57 Input
     58 
     59 ```
     60 4 4
     61 
     62 LENSE
     63 
     64 TEN
     65 
     66 SENSELESSNESSES
     67 
     68 LENSE
     69 ```
     70 
     71 Output
     72 
     73 ```
     74 3 -1 0 3
     75 ```