WC '16 Contest 4 J1 - Anyone Can Be Anything

View as PDF

Submit solution


Points: 5 (partial)
Time limit: 1.0s
Memory limit: 16M

Author:
Problem type
Woburn Challenge 2016-17 Round 4 - Junior Division

"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 \le N \le 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 \le P_i \le 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 \le O_i \le N) openings, indicating that exactly O_i new animals must be assigned to it. The total number of openings O_1 + O_2 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 Specification

The first line of input consists of a single integer N.
The second line consists of two space-separated integers O_1 and O_2.
The third line consists of N space-separated integers P_1, \dots, P_N.

Output Specification

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 2^{nd} job category, and the remaining 3 animals to the 1^{st} job category.
In this situation, all of the animals will be assigned to their preferred job category besides the 4^{th} animal, who will get stuck with job category 1 instead of 2.


Comments

There are no comments at the moment.