HungryCowsMedium | Topcoder Archive

Problem Statement

There is a herd of hungry cows. You are given the int[] cowAppetites. Each element of cowAppetites is the number of units of food one of the cows needs.

There is also a long straight road with a coordinate system. All the cows are currently standing at coordinate 0. There are some barns along the road. All barns are at distinct positive integer coordinates. You are given the positions of all barns in the int[] barnPositions. Each barn contains an unlimited supply of food. There is no other food anywhere else.

During each unit of time, each cow can choose one of three actions:

Do nothing.
Move by one unit of distance in either direction.
Eat one unit of food, if able.

A cow can only eat when it is at the same coordinate as one of the barns. Additionally, during each unit of time each barn can only serve one cow, so if there are multiple cows at a barn at the same time, only one of them can choose to eat during the next unit of time. Each cow can combine movement and eating arbitrarily. For example, a cow can move to a barn, eat 2 units of food, move to another barn, and eat 3 units of food there.

If all cows carefully make a plan, what is the earliest time in which all of them will finish eating?

Definition

Class:: HungryCowsMedium
Method:: getWellFedTime
Parameters:: int[], int[]
Returns:: long
Method signature:: long getWellFedTime(int[] cowAppetites, int[] barnPositions)
(be sure your method is public)

Constraints

cowAppetites will contain between 1 and 300 elements, inclusive.
Each element of cowAppetites will be between 1 and 1,000,000,000, inclusive.
barnPositions will contain between 1 and 300 elements, inclusive.
Each element of barnPositions will be between 1 and 1,000,000,000, inclusive.
All elements of barnPositions will be distinct.

Examples

```
{3}
```
```
{5}
```
```
Returns: 8
```
A cow that needs 3 units of food and a barn at coordinate 5. The cow will need 5 units of time to reach the barn and then another 3 units of time to eat as much as it needs.
```
{1,1,1,1,1}
```
```
{2,3}
```
```
Returns: 5
```
```
{4,4,4}
```
```
{4,2}
```
```
Returns: 9
```
The inputs are not necessarily sorted.

This problem statement is the exclusive and proprietary property of Topcoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of Topcoder, Inc. is strictly prohibited. (c)2024, Topcoder, Inc. All rights reserved.