Rupsa and Number army
All submissions for this problem are available.
Read problems statements in Mandarin Chinese , Russian and Vietnamese
Princess Rupsa came across a very interesting game. In the game, you have to face against a number army consisting of N distinct integers A1, A2, , , AN. In one move, you can shoot one magic bullet aiming at an alive enemy number, say X. The magic bullet will kill X and it will also kill X + 1 and X - 1 if they are alive when the bullet is shot. Game ends when the entire number army is killed.
Princess Rupsa wants to find out the minimum and maximum number of moves that can be played in the game. But since she has recently found her true love and is in hurry to meet him, you must help her to solve the problem as fast as possible.
- The first line of the input contains an integer T denoting the number of test cases.
- The first line of each test case contains a single integer N.
- The second line contains N space-separated integers denoting A1 to AN.
- For each test case, output a single line containing two space separated integer denoting the minimum and maximum number of moves required respectively.
- 1 ≤ T ≤ 10
- 1 ≤ N ≤ 105
- 1 ≤ Ai ≤ 106
Input: 1 3 1 2 3 Output: 1 2
- For minimum moves, you could aim for 2, killing 1, 2 and 3 in the same move.
- For maximum moves, you could aim for 1, killing 1 and 2 in the first move and then aim for 3 in the second move.
|Tags||abhra73, ad-hoc, snck151b|
|Time Limit:||1 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.5, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, SCM chicken, CLOJ, FS|
Fetching successful submissions
If you are still having problems, see a sample solution here.