Connection Status:
Competition Arena > CatsOnTheLineDiv1

CatsOnTheLineDiv1

SRM 631 · 2014-07-26 · by Witaliy

SRM 631 · 2014-07-26 · by Witaliy · Brute Force, Greedy
Class Name: CatsOnTheLineDiv1
Return Type: int
Method Name: getNumber
Arg Types: (vector<int>, vector<int>, int)
Problem Statement

Problem Statement

There are some cats sitting on a straight line that goes from the left to the right. You are given two int[]s position and count. For each valid i, there are count[i] cats initially sitting at the point position[i].

During each minute, each cat chooses and performs one of three possible actions: it may stay in its place, move one unit to the left (i.e., from x to x-1), or move one unit to the right (i.e., from x to x+1). (Note that there are no restrictions. In particular, different cats that are currently at the same point may make different choices.)

You are also given an int time. Cats don't like to sit together with other cats, so they want to minimize the number of points that contain two or more cats after time minutes. Return this minimum number.

Constraints

  • position will contain between 1 and 1,000 elements, inclusive.
  • position and count will contain the same number of elements.
  • Each element of position will be between -100,000,000 and 100,000,000, inclusive.
  • Each element of position will be distinct.
  • Each element of count will be between 1 and 100,000,000, inclusive.
  • time will be between 0 and 100,000,000, inclusive.
Examples
0)
{0}
{7}
3
Returns: 0

In this case, there are initially 7 cats at the origin. Each of the cats can go to a separate point. They will occupy all integer points from -3 to 3, inclusive. Thus, the answer is 0.

1)
{0}
{6}
2
Returns: 1

In this case, there will always be at least one point with more than one cat. One of the best strategies for the cats is to not move at all. This strategy will lead to the answer equal to 1.

2)
{4, 7, 47}
{4, 7, 4}
1
Returns: 3
3)
{3, 0, 7, 10}
{3, 7, 4, 5}
2
Returns: 2
4)
{-5, 0, 7}
{47, 85, 10}
6
Returns: 1

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

Coding Area

Language: C++17 · define a public class CatsOnTheLineDiv1 with a public method int getNumber(vector<int> position, vector<int> count, int time) · 119 test cases · 2 s / 256 MB per case

Submitting as anonymous