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≤N≤1000).

Each cow has an integer "breed ID" number in the range 1…1001…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?

 

 

 

SAMPLE INPUT:

7
1 3 5 7 9 11 13

SAMPLE OUTPUT:

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.

 

SAMPLE INPUT:

7
11 2 17 13 1 15 3

SAMPLE OUTPUT:

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

USACO 2021 January Contest, Bronze Problem 2. Even More Odd Photos 题解(翰林国际教育提供，仅供参考)

题解请注册或登录查看

[/hide]

(Analysis by Nick Wu)

In the best case, each cow is in its own group, and the answer is NN. When is this allowed to happen?

Let OO be the number of odd cows and EE be the number of even cows initially in the list. For each cow to be in its own group, either E=OE=O or E=O+1E=O+1.

If this is not the case, then we must have groups with more than one cow. There are two cases.

If E>O+1E>O+1, then the problem is that we have too many even cows. However, note that two even numbers added together is an even number. Therefore, we can do the assignment as follows - take one even cow, then one odd cow, and repeat this OO times. The remaining cows are all even, and we can put them all in the same group. In this case, the answer is 2O+12O+1.

The other case is when E<OE<O, so we have too many odd cows. Note that two odd numbers added together is an even number. To deal with having too many odd cows, we have to take two odd cows and pair them, which is equivalent to having two fewer odd cows and one more even cow. We can repeat this process of pairing two odd cows until E≥OE≥O, and then we can use the above logic to compute the answer.

Here is Brian Dean's code.

 

#include <iostream>
using namespace std;
 
int main(void)
{
  int O=0, E=0, N, x;
  cin >> N;
  for (int i=0; i<N; i++) {
    cin >> x;
    if (x % 2 == 0) E++; else O++;
  }
  while (O > E) { O=O-2; E++; }
  if (E > O+1) E = O+1;
  cout << E + O << "\n";
}

[/hide]