TopCoder problem "TwoTrains" used in TCHS07 Alpha Round 1 (Division I Level Two)



Problem Statement

    

You are at a small railway station, with only two trains departing from it. Each of the trains has a fixed time interval between its deparatures. The train to New Vasyuki departs once every t1 minutes, and the train to Old Vasyuki departs once every t2 minutes. The first departure of both trains is at time 0, so the train to New Vasyuki will depart at times 0, t1, 2*t1, and so on, while the train to Old Vasyuki will depart at times 0, t2, 2*t2, and so on.

Several people arrive at the station at different times. Each person is very impatient and takes the earliest possible departing train. Note that if a person arrives at time t, and a train departs at time t, the person will be able to catch that train. If a person needs to choose between two trains departing at the same time, he will always choose the train to New Vasyuki (see examples for further clarification). You will be given a int[] times, where each element is the time (in minutes) at which a person arrives at the station. Return the number of people who take the train to New Vasyuki.

 

Definition

    
Class:TwoTrains
Method:passengerNewVasyuki
Parameters:int, int, int[]
Returns:int
Method signature:int passengerNewVasyuki(int t1, int t2, int[] times)
(be sure your method is public)
    
 

Constraints

-t1 and t2 will be between 1 and 1000, inclusive.
-times will contain between 1 and 50 elements, inclusive.
-Each element of times will be between 0 and 10000, inclusive.
 

Examples

0)
    
1
1
{0,1,2,3,4,10000}
Returns: 6
Trains always come at the same moment. That's why all people will go to New Vasyuki.
1)
    
2
1
{0,1,2,3,4,10000}
Returns: 4
The Old Vasyuki train runs more often. People who arrive at times 0, 2, 4 and 10000 will go to New Vasyuki.
2)
    
3
2
{0,1,2,3,4,5,6,7,8,9,10}
Returns: 5
People who arrive at times 0, 3, 5, 6 and 9 will go to New Vasyuki.
3)
    
100
13
{0,13,10,2002,423,543,212,234,567,890,9876,5443,323,456,7777,8878,8787,8899,9098,23,45}
Returns: 3
4)
    
2
100
{7348,127,33,23,11}
Returns: 5

Problem url:

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

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=10702&pm=7494

Writer:

VitalyGoldstein

Testers:

PabloGilberto , brett1479 , Olexiy

Problem categories:

Simple Search, Iteration