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
slothsphereoj:
2024-02-19 04:38:03
@smso is right as of now. Those K numbers will always be included even if any pair of K numbers are consecutive. |
|
smso:
2019-04-15 11:28:34
my accepted codes give:
|
|
anirudnits:
2018-11-17 09:11:59
if any of the two given K numbers are already consecutive, then just print 0. Worked for me! |
|
nadstratosfer:
2018-04-24 19:47:04
Can't pass in raw Python and O(klogk) slower than O(n) in PyPy. Poorly set problem. |
|
singlasahil221:
2017-07-23 07:15:50
Very easy.AC in one go.O(n) solution exists. |
|
bsiddhartha:
2017-06-20 07:06:23
no sorting :) just take char array of size max n.and O(n+t)solution |
|
roshanarya905:
2017-06-18 12:28:34
qsort giving TLE why? @himanshuz1 Last edit: 2017-06-18 12:33:46 |
|
manjur1996:
2016-10-28 13:28:50
need to tighten the time.... O(n) easily excepted |
|
himanshu kumar:
2016-07-21 13:39:17
O(n+k) solution passes it easily... while sorting gives tle |
|
hodobox:
2016-07-04 07:51:27
My code does not account for the already selected numbers being consecutive |
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 |