Save More Mice codeforces solution- There are one cat, kk mice, and one hole on a coordinate line. The cat is located at the point 00, the hole is located at the point nn. All mice are located between the cat and the hole: the ii-th mouse is located at the point xixi (0

Save More Mice solution codeforces

There are one cat, kk mice, and one hole on a coordinate line. The cat is located at the point 00, the hole is located at the point nn. All mice are located between the cat and the hole: the ii-th mouse is located at the point xixi (0<xi<n0<xi<n). At each point, many mice can be located.

In one second, the following happens. First, exactly one mouse moves to the right by 11. 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 11. 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. Save More Mice solution codeforces

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).

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?

Save More Mice solution codeforces

The first line contains one integer tt (1t1041≤t≤104) — the number of test cases. Then tt test cases follow.

Each test case consists of two lines. The first line contains two integers nn and kk (2n1092≤n≤1091k41051≤k≤4⋅105). The second line contains kk integers x1,x2,xkx1,x2,…xk (1xi<n1≤xi<n) — the initial coordinates of the mice.

It is guaranteed that the sum of all kk given in the input doesn’t exceed 41054⋅105.

Save More Mice solution codeforces

For each test case output on a separate line an integer mm (m0m≥0) — the maximum number of mice that can reach the hole without being eaten.

Save More Mice solution codeforces

input

Copy
3
10 6
8 7 5 4 9 4
2 8
1 1 1 1 1 1 1 1
12 11
1 2 3 4 5 6 7 8 9 10 11

Save More Mice solution codeforces

Copy
3
1
4

Leave a Reply

Your email address will not be published. Required fields are marked *

*