NINJA5 - K NUMBERS
You are given N numbers from 1 to N. Now, your task is to choose some numbers from the N numbers (including 1 and N) such that no two numbers are consecutive. As this is easy, you are given an extra task. You have to definitely choose K numbers which are given. Find the maximum number of numbers that you can choose in such a way.
Input:
The first line has an integer T, the number of test cases.
Then for each test case, the first line has two integers N and K.
Then the next line has K numbers which you should definitely choose.
Output:
For each test case, print the maximum number of numbers that you can choose.
Constraints:
1 <= T <= 100
2 <= N <= 2 x 10^6
1 <= K <= N / 2
1 <= X[1...K] <= N
Sample
Input:
1
8 2
6 2
Output:
4
Input: 1 8 2 6 2 Output: 4
hide comments
Piyush Kumar:
2016-06-19 20:58:36
If the question can be done in O(n), I think the constraints can be a little tighter. My O(nlogn) passed comfortably! |
|
Admin Deepak Baghel:
2016-06-09 12:54:58
i think there is bug in test cases may be any two of the given K numbers are consecutive already. Last edit: 2016-06-09 12:59:49 |
|
Sushovan Sen:
2016-05-30 13:30:35
Are values of k sorted? |
|
sri:
2016-02-28 10:17:53
O(n) accepting Last edit: 2016-02-28 10:18:12 |
|
lalit_nit:
2016-02-25 06:23:53
smone provide any tricky tst case please.....
|
|
Siddharth Singh:
2016-02-21 11:20:38
Easy Problem if u get the logic
|
|
Prateek Agarwal:
2016-02-21 08:00:24
time limit for python is strict. Python 2.7.10 code gives TLE.same code in C++ 5.1 passes in 0.07s |
|
Sankaranarayanan G:
2016-02-21 07:14:08
Thanks @Ankit |
|
Ankit:
2016-02-20 21:16:23
Lovey Problem. :) @mombassa
|
Added by: | mombassa |
Date: | 2016-02-17 |
Time limit: | 0.200s-1s |
Source limit: | 50000B |
Memory limit: | 1536MB |
Cluster: | Cube (Intel G860) |
Languages: | All except: ASM64 GOSU JS-MONKEY |