#PU1084. USACO 2021 January Contest, Bronze — Problem 2. Even More Odd Photos

USACO 2021 January Contest, Bronze — Problem 2. Even More Odd Photos

USACO 2021 January Contest, Bronze — Problem 2. Even More Odd Photos

题目描述

Farmer John is yet again trying to take a photograph of his NN cows (2≤N≤10002 \leq N \leq 1000). Each cow has an integer "breed ID" number in the range 1…1001 \ldots 100. Farmer John has a very peculiar idea in mind for his photo: he wants to partition all the cows into disjoint groups (in other words, place each cow in exactly one group) and then line up the groups so the sum of the breed IDs of the cows in the first group is even, the sum of the IDs in the second group is odd, and so on, alternating between even and odd. What is the maximum possible number of groups Farmer John can form?

输入格式

The first line of input contains NN. The next line contains NN space-separated integers giving the breed IDs of the NN cows.

输出格式

The maximum possible number of groups in Farmer John's photo. It can be shown that at least one feasible grouping exists.

数据范围

(见题面原文)

样例

样例 1

7
1 3 5 7 9 11 13
3
In this example, one way to form the maximum number of three groups is as
follows. Place 1 and 3 in the first group, 5, 7, and 9 in the second group, and
11 and 13 in the third group.

样例 2

7
11 2 17 13 1 15 3
5
In this example, one way to form the maximum number of five groups is as
follows. Place 2 in the first group, 11 in the second group, 13 and 1 in the
third group, 15 in the fourth group, and 17 and 3 in the fifth group.
Problem credits: Nick Wu