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 Pi (1 ≤ Pi ≤ 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 Oi (0 ≤ Oi ≤ N) openings, indicating that exactly Oi new animals must be assigned to it. The total number of openings O1 + O2 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?
The first line of input consists of a single integer N.
The second line consists of two space-separated integers O1 and O2.
The third line consists of N space-separated integers P1, …, PN.
Output a single line consisting of a single integer – the maximum number of animals who can be assigned to their preferred job category.
5 3 2 2 1 1 2 2
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.
Point Value: 5 (partial)
Time Limit: 2.00s
Memory Limit: 16M
Added: Apr 09, 2017
C++03, PAS, C, HASK, ASM, RUBY, PYTH2, JAVA, PHP, SCM, CAML, PERL, C#, C++11, PYTH3