Problem: Hiring Monks

• Problem statement
• Hall of fame
• Return to hub

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

Hiring Monks

Input File: hirein.txt
Output File: hireout.txt
Time Limit: 1 second
Memory Limit: 1 GB

High up in the peaks of Kosciuszko National Park, an elite sect of monks are deciding how to assign jobs to the new monks.

They have hired N new monks, numbered from 1 to N, each possessing a possibly different skill level. The monk i has a skill level of x_i.

There are S student jobs available, numbered from 1 to S, created for monks to learn from their masters. As such, there is a limit on how much skill a monk can have for this job. Student job j is available to monks with a skill level at most s_j.

There are M master jobs available, numbered from 1 to M, created for monks to teach their students. As such, there is a minimum skill level a monk must have for this job. Master job k is available to monks with a skill level at least m_k.

Each monk can be assigned at most one job, and each job can be assigned to at most one monk. What is the largest number of monks you can assign to jobs?

Input

• The first line contains the integer N, the number of monks. Then, N lines follow. The ith of these lines contains the integer x_i, the skill level of monk i.
• The next line contains the integer S, the number of student jobs (which could be zero). Then, S lines follow. The jth of these lines contains the integer s_j.
• The next line contains the integer M, the number of master jobs (which could be zero). Then, M lines follow. The kth of these lines contains the integer m_k.

Output

Your program should output a single integer: the maximum number of monks who can be assigned to jobs.

Sample Input 1

5
100
300
20
40
1000
2
50
110
3
300
2500
600

Sample Output 1

4

Sample Input 2

4
10
10
20
20
3
15
100
100
0

Sample Output 2

3

Explanation

In the first sample input, one way you can assign the monks is as follows:

This assigns four monks, which is the maximum possible.

In the second sample input, one way you can assign the monks is as follows:

This assigns three monks, which is the maximum possible.

Subtasks & Constraints

For all cases:

• 1 ≤ N ≤ 100,000.
• 0 ≤ S ≤ 100,000.
• 0 ≤ M ≤ 100,000.
• 1 ≤ x_i ≤ 1,000,000,000 for all i.
• 1 ≤ s_j ≤ 1,000,000,000 for all j.
• 1 ≤ m_k ≤ 1,000,000,000 for all k.

Furthermore:

• For Subtask 1 (15 marks), s_j = 10, for all j, and m_k = 10, for all k.

  Hint: This subtask says the skill level limit for student jobs, and the minimum skill level for master jobs, is always 10. This means the only thing that matters about each monk, is whether their skill is less than 10, more than 10, or equal to 10.

• For Subtask 2 (15 marks), s_j = 200, for all j, and m_k = 100, for all k.

  Hint: The solution to this subtask is quite similar to Subtask 1.

• For Subtask 3 (30 marks), S = 0, N ≤ 1000 and M ≤ 1000. In particular, S = 0 means that there are no student jobs; there are only master jobs.

  Hint: To start with, ask yourself which monk should be assigned to the master job requiring the most skill.

• For Subtask 4 (20 marks), S = 0. There are no student jobs; there are only master jobs.

  Hint: The input is quite large in this subtask, so you will need a fast solution. Try to avoid nested loops. Maybe sorting will help?

• For Subtask 5 (20 marks), no further constraints apply.

  There are no hints available for this subtask.

 

Page generated: 25 March 2023,  5:59pm AEDT