codeforces-scrape

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

1790D.md (2725B)


      1 Source: https://codeforces.com/problemset/problem/1790/D
      2 
      3 D. Matryoshkas
      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 standard input
     16 
     17 output
     18 
     19 standard output
     20 
     21 Matryoshka is a wooden toy in the form of a painted doll, inside which you can put a similar doll of a smaller size.
     22 
     23 A set of nesting dolls contains one or more nesting dolls, their sizes are consecutive positive integers. Thus, a set of nesting dolls is described by two numbers: $s$ — the size of a smallest nesting doll in a set and $m$ — the number of dolls in a set. In other words, the set contains sizes of $s, s + 1, \dots, s + m - 1$ for some integer $s$ and $m$ ($s,m \gt 0$).
     24 
     25 You had one or more sets of nesting dolls. Recently, you found that someone mixed all your sets in one and recorded a sequence of doll sizes — integers $a_1, a_2, \dots, a_n$.
     26 
     27 You do not remember how many sets you had, so you want to find the minimum number of sets that you could initially have.
     28 
     29 For example, if a given sequence is $a=[2, 2, 3, 4, 3, 1]$. Initially, there could be $2$ sets:
     30 
     31 * the first set consisting of $4$ nesting dolls with sizes $[1, 2, 3, 4]$;
     32 * a second set consisting of $2$ nesting dolls with sizes $[2, 3]$.
     33 
     34 According to a given sequence of sizes of nesting dolls $a_1, a_2, \dots, a_n$, determine the minimum number of nesting dolls that can make this sequence.
     35 
     36 Each set is completely used, so all its nesting dolls are used. Each element of a given sequence must correspond to exactly one doll from some set.
     37 
     38 Input
     39 
     40 The first line of input data contains a single integer $t$ ($1 \le t \le 10^4$) — the number of test cases.
     41 
     42 The description of the test cases follows.
     43 
     44 The first line of each test case contains one integer $n$ ($1 \le n \le 2 \cdot 10^5$) — the total number of matryoshkas that were in all sets.
     45 
     46 The second line of each test case contains $n$ integers $a_1, a_2, \dots, a_n$ ($1 \le a_i \le 10^9$)  — the sizes of the matryoshkas.
     47 
     48 It is guaranteed that the sum of values of $n$ over all test cases does not exceed $2\cdot10^5$.
     49 
     50 Output
     51 
     52 For each test case, print one integer $k$ — the minimum possible number of matryoshkas sets.
     53 
     54 Example
     55 
     56 Input
     57 
     58 ```
     59 10
     60 
     61 6
     62 
     63 2 2 3 4 3 1
     64 
     65 5
     66 
     67 11 8 7 10 9
     68 
     69 6
     70 
     71 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000
     72 
     73 8
     74 
     75 1 1 4 4 2 3 2 3
     76 
     77 6
     78 
     79 1 2 3 2 3 4
     80 
     81 7
     82 
     83 10 11 11 12 12 13 13
     84 
     85 7
     86 
     87 8 8 9 9 10 10 11
     88 
     89 8
     90 
     91 4 14 5 15 6 16 7 17
     92 
     93 8
     94 
     95 5 15 6 14 8 12 9 11
     96 
     97 5
     98 
     99 4 2 2 3 4
    100 ```
    101 
    102 Output
    103 
    104 ```
    105 2
    106 1
    107 6
    108 2
    109 2
    110 2
    111 2
    112 2
    113 4
    114 3
    115 ```
    116 
    117 Note
    118 
    119 The first test case is described in the problem statement.
    120 
    121 In the second test case, all matryoshkas could be part of the same set with minimum size $s=7$.
    122 
    123 In the third test case, each matryoshka represents a separate set.