USACO 2021 January Contest Bronze Division - Even More Odd Photos

Problem link: here

Solution Author: Stefan Dascalescu

Problem Solution

Fix the number of odd groups and then check if we have enough odds and eligible evens to get it done.

Source codes

The source codes in C++ and Python can be seen below.

#include <bits/stdc++.h>
using namespace std;

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n;
    cin >> n;

    int odd = 0, even = 0;
    for(int i = 0; i < n; i++)
    {
        int x;
        cin >> x;

        if(x % 2)
            odd++;
        else
            even++;
    }

    for(int i = n; i >= 1; i--)
    {
        int evengroups = i/2 + i%2;
        int oddgroups = i/2;
        if(odd >= oddgroups)
        {
            int remodd = odd - oddgroups;
            if(remodd % 2 == 0 && remodd/2 + even >= evengroups)
            {
                cout << i;
                return 0;
            }
        }
    }
    return 0;
}

n = int(input())
v = list(map(int, input().split()))

odd = sum(1 for x in v if x % 2)
even = n - odd

for i in range(n, 0, -1):
    evengroups = i // 2 + i % 2
    oddgroups = i // 2
    if odd >= oddgroups:
        remodd = odd - oddgroups
        if remodd % 2 == 0 and remodd // 2 + even >= evengroups:
            print(i)
            break