codeforces-scrape

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

1593C.md (2123B)


      1 Source: https://codeforces.com/problemset/problem/1593/C
      2 
      3 C. Save More Mice
      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 one cat, $k$ mice, and one hole on a coordinate line. The cat is located at the point $0$, the hole is located at the point $n$. All mice are located between the cat and the hole: the $i$-th mouse is located at the point $x_i$ ($0 \lt x_i \lt n$). At each point, many mice can be located.
     22 
     23 In one second, the following happens. First, exactly one mouse moves to the right by $1$. If the mouse reaches the hole, it hides (i.e. the mouse will not any more move to any point and will not be eaten by the cat). Then (after that the mouse has finished its move) the cat moves to the right by $1$. If at the new cat's position, some mice are located, the cat eats them (they will not be able to move after that). The actions are performed until any mouse hasn't been hidden or isn't eaten.
     24 
     25 In other words, the first move is made by a mouse. If the mouse has reached the hole, it's saved. Then the cat makes a move. The cat eats the mice located at the pointed the cat has reached (if the cat has reached the hole, it eats nobody).
     26 
     27 Each second, you can select a mouse that will make a move. What is the maximum number of mice that can reach the hole without being eaten?
     28 
     29 Input
     30 
     31 The first line contains one integer $t$ ($1 \le t \le 10^4$) — the number of test cases. Then $t$ test cases follow.
     32 
     33 Each test case consists of two lines. The first line contains two integers $n$ and $k$ ($2 \le n \le 10^9$, $1 \le k \le 4 \cdot 10^5$). The second line contains $k$ integers $x_1, x_2, \dots x_k$ ($1 \le x_i \lt n$) — the initial coordinates of the mice.
     34 
     35 It is guaranteed that the sum of all $k$ given in the input doesn't exceed $4 \cdot 10^5$.
     36 
     37 Output
     38 
     39 For each test case output on a separate line an integer $m$ ($m \ge 0$) — the maximum number of mice that can reach the hole without being eaten.
     40 
     41 Example
     42 
     43 Input
     44 
     45 ```
     46 3
     47 10 6
     48 8 7 5 4 9 4
     49 2 8
     50 1 1 1 1 1 1 1 1
     51 12 11
     52 1 2 3 4 5 6 7 8 9 10 11
     53 ```
     54 
     55 Output
     56 
     57 ```
     58 3
     59 1
     60 4
     61 ```