Woburn Challenge 2016-17 Round 4 - Junior Division

Problem 1: Anyone Can Be Anything

"I don't have to cower in a herd anymore. Instead, I can be an astronaut!"
"I don't have to be a lonely hunter anymore. Today I can hunt for tax exemptions; I'm gonna be an actuary!"
"And I can make the world a better place, I am going to be… a police officer!"

In an ever more progressive and open-minded society, Zootopia's slogan "Anyone can be Anything" is becoming a reality at last. Its animal inhabitants are no longer strictly bound to traditional professions based on their species, and are instead free to pursue any careers that they please.

There are 2 different categories of jobs in Zootopia, with jobs which have typically been performed by predators falling into category 1, and jobs traditionally associated with prey falling into category 2. There are also N (1 ≤ N ≤ 15) young animals who are preparing to join the workforce. Each animal will get assigned to one of the job categories. However, their assignment will no longer be dictated by their species – instead, the i-th animal will apply for their preferred job category P_i (1 ≤ P_i ≤ 2), and will have a fair shot of getting a spot in it, with the help of the city's strict anti-discrimination hiring laws.

Unfortunately, however, even the overcoming of deep-rooted social prejudices doesn't mean that everyone can end up happy. For example, even if everybody wants to become an astronaut, society can realistically only continue running smoothly if the majority of its members contribute in more practical roles, regardless of their wishes. To that end, the i-th job category has O_i (0 ≤ O_i ≤ N) openings, indicating that exactly O_i new animals must be assigned to it. The total number of openings O₁ + O₂ is equal to the number of animals N, meaning that once every animal has been assigned to a job category, both categories' openings should be exactly filled.

Perhaps everyone can't be anything, but at least some animals can be allowed to live out their dreams. Once all N animals have been assigned to job categories in some valid fashion, what's the maximum number of animals which can end up having been assigned to their preferred job category?

Input Format

The first line of input consists of a single integer N.
The second line consists of two space-separated integers O₁ and O₂.
The third line consists of N space-separated integers P₁, …, P_N.

Output Format

Output a single line consisting of a single integer – the maximum number of animals who can be assigned to their preferred job category.

Sample Input

5
3 2
2 1 1 2 2

Sample Output

4

Sample Explanation

One optimal arrangement is to assign the first and last animals to the 2nd job category, and the remaining 3 animals to the 1st job category.
In this situation, all of the animals will be assigned to their preferred job category besides the 4th animal, who will get stuck with job category 1 instead of 2.

All Submissions
Best Solutions

Point Value: 5 (partial)
Time Limit: 2.00s
Memory Limit: 16M
Added: Apr 09, 2017
Author: SourSpinach

Languages Allowed:
C++03, PAS, C, HASK, ASM, RUBY, PYTH2, JAVA, PHP, SCM, CAML, PERL, C#, C++11, PYTH3

Comments (Search)