Connection Status:
Competition Arena > TransportCounting

TransportCounting

SRM 207 · 2004-08-10 · by Olexiy

SRM 207 · 2004-08-10 · by Olexiy · Brute Force, Simple Math
Class Name: TransportCounting
Return Type: int
Method Name: countBuses
Arg Types: (int, vector<int>, vector<int>, int)
Problem Statement

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.

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 two 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 both buses.

3)
998
{1000, 1, 1000}
{997, 998, 0}
999
Returns: 1
4)
564
{}
{}
607
Returns: 0

The street is empty.

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

Coding Area

Language: C++17 · define a public class TransportCounting with a public method int countBuses(int speed, vector<int> positions, vector<int> velocities, int time) · 71 test cases · 2 s / 256 MB per case

Submitting as anonymous