codeforces-scrape

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

1077D.md (2670B)


      1 Source: https://codeforces.com/problemset/problem/1077/D
      2 
      3 D. Cutting Out
      4 
      5 time limit per test
      6 
      7 3 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 You are given an array $s$ consisting of $n$ integers.
     22 
     23 You have to find any array $t$ of length $k$ such that you can cut out maximum number of copies of array $t$ from array $s$.
     24 
     25 Cutting out the copy of $t$ means that for each element $t_i$ of array $t$ you have to find $t_i$ in $s$ and remove it from $s$. If for some $t_i$ you cannot find such element in $s$, then you cannot cut out one more copy of $t$. The both arrays can contain duplicate elements.
     26 
     27 For example, if $s = [1, 2, 3, 2, 4, 3, 1]$ and $k = 3$ then one of the possible answers is $t = [1, 2, 3]$. This array $t$ can be cut out $2$ times.
     28 
     29 * To cut out the first copy of $t$ you can use the elements $[1, \underline{\textbf{2}}, 3, 2, 4, \underline{\textbf{3}}, \underline{\textbf{1}}]$ (use the highlighted elements). After cutting out the first copy of $t$ the array $s$ can look like $[1, 3, 2, 4]$.
     30 * To cut out the second copy of $t$ you can use the elements $[\underline{\textbf{1}}, \underline{\textbf{3}}, \underline{\textbf{2}}, 4]$. After cutting out the second copy of $t$ the array $s$ will be $[4]$.
     31 
     32 Your task is to find such array $t$ that you can cut out the copy of $t$ from $s$ maximum number of times. If there are multiple answers, you may choose any of them.
     33 
     34 Input
     35 
     36 The first line of the input contains two integers $n$ and $k$ ($1 \le k \le n \le 2 \cdot 10^5$) — the number of elements in $s$ and the desired number of elements in $t$, respectively.
     37 
     38 The second line of the input contains exactly $n$ integers $s_1, s_2, \dots, s_n$ ($1 \le s_i \le 2 \cdot 10^5$).
     39 
     40 Output
     41 
     42 Print $k$ integers — the elements of array $t$ such that you can cut out maximum possible number of copies of this array from $s$. If there are multiple answers, print any of them. The required array $t$ can contain duplicate elements. All the elements of $t$ ($t_1, t_2, \dots, t_k$) should satisfy the following condition: $1 \le t_i \le 2 \cdot 10^5$.
     43 
     44 Examples
     45 
     46 Input
     47 
     48 ```
     49 7 3
     50 1 2 3 2 4 3 1
     51 ```
     52 
     53 Output
     54 
     55 ```
     56 1 2 3
     57 ```
     58 
     59 Input
     60 
     61 ```
     62 10 4
     63 1 3 1 3 10 3 7 7 12 3
     64 ```
     65 
     66 Output
     67 
     68 ```
     69 7 3 1 3
     70 ```
     71 
     72 Input
     73 
     74 ```
     75 15 2
     76 1 2 1 1 1 2 1 1 2 1 2 1 1 1 1
     77 ```
     78 
     79 Output
     80 
     81 ```
     82 1 1
     83 ```
     84 
     85 Note
     86 
     87 The first example is described in the problem statement.
     88 
     89 In the second example the only answer is $[7, 3, 1, 3]$ and any its permutations. It can be shown that you cannot choose any other array such that the maximum number of copies you can cut out would be equal to $2$.
     90 
     91 In the third example the array $t$ can be cut out $5$ times.