#K15976. Optimal Crop Allocation
Optimal Crop Allocation
Optimal Crop Allocation
You are given f fields and c crop types. Each field has a capacity and each crop type requires a specific amount of space. A field i with size \(S_i\) can only be used to plant a crop type j if the crop's space requirement \(R_j\) satisfies \(R_j \leq S_i\). Each field can accommodate at most one crop and each crop type can only be planted once. Your task is to determine the maximum number of distinct crop types that can be planted across the fields.
In other words, find the maximum matching between the fields and the crops under the constraint:
[ R_j \leq S_i \quad \text{for the assigned crop } j \text{ to field } i. ]
The input contains several datasets. Each dataset starts with two integers, f and c, which represent the number of fields and the number of crop types respectively. It is followed by f integers representing the field sizes and then c integers representing the space required for each crop type. A dataset with f = 0 and c = 0 indicates the end of input.
inputFormat
The input is read from the standard input (stdin) and consists of several datasets. Each dataset is structured as follows:
- The first line contains two integers:
f
(the number of fields) andc
(the number of crop types). - The second line contains
f
integers representing the sizes of the fields. - The third line contains
c
integers representing the space required for each crop type.
The input terminates with a line where both f
and c
are 0. Each dataset (except the terminating one) should be processed, and the corresponding result printed in order.
outputFormat
For each dataset, output a single integer on a new line representing the maximum number of different crop types that can be planted under the given constraints.
## sample3 4
10 8 5
3 6 4 2
8 3
20 15 10 25 30 10 20 15
10 20 15
2 2
5 15
5 10
0 0
3
3
2
</p>