Even More Odd Photos

题目描述

农夫约翰又一次想给他的 $N$ 头奶牛拍照（$2 \leq N \leq 1000$）。 每头奶牛都有一个整数的“品种 ID”，范围为 $1 \ldots 100$。农夫约翰对这张照片有一个非常特别的想法：他想把所有奶牛划分成若干互不相交的组（换句话说，每头奶牛恰好属于一个组），然后将这些组排成一列，使得第一组中奶牛的品种 ID 之和为偶数，第二组的 ID 之和为奇数，如此交替出现偶数与奇数。 问：农夫约翰最多可以组成多少个组？

输入格式

第一行输入 $N$。 第二行输入 $N$ 个用空格分隔的整数，表示这 $N$ 头奶牛的品种 ID。

输出格式

输出农夫约翰照片中可能的最大组数。 可以证明至少存在一种可行的分组方案。

7
1 3 5 7 9 11 13

3

7
11 2 17 13 1 15 3

5

提示

在这个例子中，一种组成最多 3 个组的方法如下：将 1 和 3 放入第一组，将 5、7 和 9 放入第二组，将 11 和 13 放入第三组。

在这个例子中，一种组成最多 5 个组的方法如下：将 2 放入第一组，将 11 放入第二组，将 13 和 1 放入第三组，将 15 放入第四组，将 17 和 3 放入第五组。

题目来源：Nick Wu

标签: USACO|2021|Bronze

来源

USACO|2021|Bronze