Chef and Game with Sequence
All submissions for this problem are available.
Read problems statements in Mandarin chinese, Russian and Vietnamese as well.
Chef has a sequence A containing N integers A1, A2, ..., AN.
Chef is playing a game with this sequence. In this game, he may perform the following operation any number of times (including zero): Choose an arbitrary pair of elements from the sequence such that their sum is even, delete these two elements from the sequence and insert their sum into the sequence instead.
The goal of the game is to minimise the number of elements in the sequence.
Help Chef to play the game and find the minimum possible size of the sequence at the end of the game!
- The first line of the input contains a single integer T denoting the number of test cases. The description of T test cases follows.
- The first line of each test case contains a single integer N.
- The second line contains N space-separated integers A1, A2, ..., AN.
For each test case, print a single line containing one integer — the minimum possible final size of the sequence.
- 1 ≤ T ≤ 100
- 1 ≤ N ≤ 100
- 1 ≤ Ai ≤ 1,000 for each valid i
Subtask #1 (100 points): original constraints
Input: 2 2 1 2 5 7 4 3 2 6 Output: 2 1
Example case 1: There is no pair of elements with an even sum. Thus, the sequence must remain the same and the answer is 2.
Example case 2: Chef can choose elements 7 and 3 in the first step, delete them and insert 10 in the sequence. Now all its elements are even and Chef can choose any two elements on each of the following steps of the game until the sequence contains only one element.
|Tags||cakewalk, kefaa, ltime56, taran_1407|
|Time Limit:||0.5 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.6, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, rust, SCALA, swift, 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, kotlin, PERL6, TEXT, SCM chicken, PYP3, CLOJ, COB, FS|
Fetching successful submissions
If you are still having problems, see a sample solution here.