AIOC Banner

Problem: Restaurants

Want to try solving this problem? You can submit your code online if you log in or register.


Input File: restin.txt
Output File: restout.txt
Time Limit: 1 second

You are the organiser for the Youth United Nations Conference which is being held this year in Le Nourse, Switzerland. It is the first night and you need to find somewhere for everybody to eat, but having forgotten to book, the local restaurants are nearly full and only have limited seating left.

Due to the important political nature of the Youth UN, it is crucial that no two delegates from the same country eat at the same restaurant. This will force them to meet the delegates from other countries and get to work on solving the world's problems.

However, because of the limited seating, this arrangement may not be possible--in particular, some delegates may not be able to eat at a restaurant. You would like to minimise the number of delegates that miss out so as not to cause an international incident.

Knowing that the fate of the world's future political leaders rests solely on your shoulders, you whip out your trusty laptop and set about determining the fewest number of delegates that will be forced to go hungry.


The input file will contain a description of the countries and a description of the available restaurants.

The first line of input will contain a single integer n, representing the number of countries attending the conference ( 0  <= n  <= 5000). Following this will be a line containing n integers, giving the number of delegates from each country. These integers will be separated by spaces, and each will be between 1 and 20 inclusive.

The third line of input will contain a single integer m, representing the number of available restaurants ( 0  <= m  <= 5000). Following this will be a line containing m integers, giving the number of seats available in each restaurant. These integers will again be separated by spaces, and each will be between 1 and 100 inclusive.


Your output file must consist of a single line containing a single integer, the total number of delegates that cannot be seated at a restaurant.

Sample Input 1

3 3
4 3 4

Sample Output 1



The example above is a simple one, since every delegate can be seated. Here there are two countries at the conference, each with 3 delegates. There are also 3 restaurants. The first and third restaurants have 4 seats available, and the second restaurant has 3 seats available.

The delegates are easy to seat in this case--simply place one member of each team in each restaurant. Since every restaurant has more than two seats available, everybody can be seated and nobody misses out.

Sample Input 2

4 3 3
5 2 3

Sample Output 2



The second example above is more difficult. Here the first country has more delegates than there are restaurants, so at least one of its delegates must miss out. Moreover, the second restaurant only has space for delegates from two countries, and so a second delegate must miss out. It is possible however to arrange the seating so that only two delegates miss out overall, and so the final solution is two.


The score for each input scenario will be 100% if the correct answer is written to the output file, and 0% otherwise.


Privacy statement
© Australian Mathematics Trust 2001-2023

Page generated: 25 March 2023,  6:15pm AEDT