Connection Status:
Competition Arena > Mosquitoes

Mosquitoes

SRM 528 · 2011-05-25 · by ir5

SRM 528 · 2011-05-25 · by ir5 · Geometry, Math
Class Name: Mosquitoes
Return Type: int
Method Name: getMaximum
Arg Types: (vector<int>, vector<int>, int)
Problem Statement

Problem Statement

One day, Fox Ciel got surprised because there were many mosquitoes in her garden. She decided to kill as many mosquitoes as possible by detonating a single bomb at a suitable place and time.

Ciel's garden can be seen as an infinitely long straight line. Mosquitoes are points, each moving with some constant velocity. You are given int[]s xInit and v of equal length N. For each i between 0 and N-1, inclusive, there is a mosquito with current position xInit[i] and constant velocity v[i].

The current positions all correspond to a moment at time t=0. A mosquito that starts at the position X and has velocity V will be at the position X+Vt at time t. For example, a mosquito with velocity 0 stays at the same position forever, and two mosquitoes with velocities -1 and 1 are flying in opposite directions.

You are also given an int R: the radius of Ciel's bomb. If a bomb is detonated at the position x at time t, it kills all mosquitoes that are at positions between x-R and x+R, inclusive, at that time. The position of the bomb and the time of detonation do not have to be integers. Ciel can detonate the bomb at any nonnegative time t (including t=0). Your method must return the maximum number of mosquitoes she can kill by a single detonation.

Constraints

  • xInit will contain between 1 and 50 elements, inclusive.
  • xInit and v will contain the same number of elements.
  • Each element of xInit will be between -100 and 100, inclusive.
  • Each element of v will be between -100 and 100, inclusive.
  • All elements in v will be pairwise distinct.
  • R will be between 1 and 100, inclusive.
Examples
0)
{1, -1}
{1, -1}
10
Returns: 2

There are many ways how to kill both mosquitoes. For example, she can detonate the bomb at time t=0 at position 0.

1)
{100, -100}
{1, -1}
10
Returns: 1

In this case, Ciel can only kill one mosquito. Note that the two mosquitoes are flying away from each other.

2)
{0, -1, 10, -11, 99, -99}
{1, -1, -3, 3, 47, -47}
3
Returns: 4

In this case, an optimal solution is to detonate the bomb at position -0.5 at the time t=2.5. Mosquitoes 0, 1, 2, and 3 will be killed by the bomb.

3)
{5}
{2}
8
Returns: 1
4)
{12,34,56,78,90}
{-1,2,-3,4,-5}
6
Returns: 3

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

Coding Area

Language: C++17 · define a public class Mosquitoes with a public method int getMaximum(vector<int> xInit, vector<int> v, int R) · 116 test cases · 2 s / 256 MB per case

Submitting as anonymous