TopCoder problem "TransportCounting" used in SRM 207 (Division II Level One)



Problem Statement

    You are studying public transportation, and you want to know how many buses are going down a particular one-way street every minute. You are driving along the street by car, and counting the buses you meet or overtake. After some time, you stop counting and report the result. In this problem, you may assume that the street is a straight line, and that your car and all of the buses can only go along this line in the same direction.



You will be given an int, speed, giving your speed in meters per minute. You will also be given a int[] positions, specifying how far ahead of you each of the buses is in meters at time 0, and a int[] velocities, specifying the velocities of the buses in meters per minute. The ith element of velocities and the ith element of positions specify the velocity and position of the ith bus, respectively. Finally, an int, time, tells you how many minutes you should count the buses you pass for.



You should return the number of buses you will overtake or meet during time minutes. If you meet one or several buses at the first or at the final moment, count them also.
 

Definition

    
Class:TransportCounting
Method:countBuses
Parameters:int, int[], int[], int
Returns:int
Method signature:int countBuses(int speed, int[] positions, int[] velocities, int time)
(be sure your method is public)
    
 

Constraints

-positions and velocities will contain the same number of elements.
-positions will contain between 0 and 50 elements, inclusive.
-speed and time will both be between 0 and 1000 inclusive.
-All elements of positions and velocities will be between 0 and 1000, inclusive.
 

Examples

0)
    
100
{0}
{0}
0
Returns: 1
Though the duration of your counting is 0, you still can count the first bus.
1)
    
5
{10, 10}
{0, 1}
2
Returns: 1
There are four buses.

The first bus starts 10 meters from you and does not move - so you will reach it in the final moment of your measurement.

The second bus starts from the same point as the first one, but goes away from you, covering 1 meter per minute. Thus you won't catch it.
2)
    
5
{10, 10}
{0, 1}
3
Returns: 2
The same example as before, except time is equal to 3 minutes. This extra minute allows you to meet three buses.
3)
    
777
{10,20,30,40,50,60,70,80,90,100,
110,120,130,140,150,160,170,180,190,200,
210,220,230,240,250,260,270,280,290,300,
310,320,330,340,350,360,370,380,390,400,
410,420,430,440,450,460,470,480,490,500}
{10,20,30,40,50,60,70,80,90,100,
110,120,130,140,150,160,170,180,190,200,
210,220,230,240,250,260,270,280,290,300,
310,320,330,340,350,360,370,380,390,400,
410,420,430,440,450,460,470,480,490,500}
333
Returns: 50
4)
    
5
{0,0,0}
{4,5,6}
10
Returns: 3

Problem url:

http://www.topcoder.com/stat?c=problem_statement&pm=2928

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=5853&pm=2928

Writer:

Olexiy

Testers:

PabloGilberto , lbackstrom , brett1479

Problem categories:

Brute Force, Simple Math