Connection Status:
Competition Arena > HungryCowsMedium

HungryCowsMedium

TCO 19 SRM 739 · 2018-10-09 · by Blue.Mary

TCO 19 SRM 739 · 2018-10-09 · by Blue.Mary · Greedy
Class Name: HungryCowsMedium
Return Type: long
Method Name: getWellFedTime
Arg Types: (vector<int>, vector<int>)
Problem Statement

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?

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
0)
{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,1}
{2,3}
Returns: 5
2)
{4,4,4}
{4,2}
Returns: 9

The inputs are not necessarily sorted.

3)
{13,6,15}
{999999994,1000000000}
Returns: 1000000014
4)
{1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1}
{167,33,138,18,56,67,77,108,102,176,122,200,84,100,85,12,129,97,76,51,165,46,4,119,170,32,164,9,150,50,179,189,16,60,80,197,43,45,22,35,41,75,15,132,117,142,38,36,131,180,74,141,101,19,68,191,87,44,34,156,82,83,128,114,98,99,81,72,121,79,3,94,181,157,11,58,20,136,91,49,144,110,103,137,111,29,153,59,13,145,47,133,93,10,184,95,92,1,62,187,162,96,23,198,14,130,109,88,115,55,125,126,192,127,166,168,149,40,52,30,159,195,24,186,89,199,25,120,61,116,196,31,173,178,28,135,147,177,21,152,86,53,172,7,17,123,48,104,65,146,171,78,113,151,193,183,73,118,70,174,106,66,185,63,160,188,105,107,57,8,69,112,124,6,26,64,134,39,163,54,139,5,161,154,175,143,155,158,194,182,148,169,42,71,27,90,140,37,190,2}
Returns: 25

Submissions are judged against all 45 archived test cases, of which 5 are shown here. Case numbers match the judge’s.

Coding Area

Language: C++17 · define a public class HungryCowsMedium with a public method long long getWellFedTime(vector<int> cowAppetites, vector<int> barnPositions) · 45 test cases · 2 s / 256 MB per case

Submitting as anonymous