TopCoder problem "BusAwaiting" used in TCO08 Qual 2 (Division I Level One)



Problem Statement

    

There is a bus stop near your home. The daily bus routes are given in the String[] buses, each element of which is formatted "START INTERVAL COUNT" (quotes for clarity). Each element describes a single route consisting of COUNT buses. The first bus on the route comes at time START, and the interval between each pair of consecutive buses is INTERVAL. In other words, the buses on that route come at times START, START + INTERVAL, ..., START + (COUNT - 1) * INTERVAL.

You arrive at the bus stop at time arrivalTime. Return the amount of time you must wait before the next bus (from any of the given routes) comes to your stop. If there's a bus at the stop at the exact moment you arrive, return 0. If no buses come for the rest of the day, return -1.

 

Definition

    
Class:BusAwaiting
Method:waitingTime
Parameters:String[], int
Returns:int
Method signature:int waitingTime(String[] buses, int arrivalTime)
(be sure your method is public)
    
 

Constraints

-buses will contain between 1 and 50 elements, inclusive.
-Each element of buses will be formatted "START INTERVAL COUNT" (quotes for clarity), where START, INTERVAL and COUNT are integers with no leading zeros.
-Each START will be between 1 and 1,000,000, inclusive.
-Each INTERVAL will be between 1 and 10,000, inclusive.
-Each COUNT will be between 1 and 100, inclusive.
-arrivalTime will be between 1 and 1,000,000, inclusive.
 

Examples

0)
    
{"150 50 10"}
285
Returns: 15
There is only one bus route. The buses come at times 150, 200, 250, ..., 600. You arrive at time 285 and you're able to catch a bus at time 300.
1)
    
{"123456 10000 1"}
123456
Returns: 0
You are lucky to catch the one and only bus at the exact moment it arrives.
2)
    
{"270758 196 67",
 "904526 8930 66",
 "121164 3160 56"}
1
Returns: 121163
You arrive very early, but all the buses start quite late.
3)
    
{"718571 2557 74",
 "480573 9706 54",
 "16511 6660 90"}
1000000
Returns: -1
By the time you arrive, all the buses have already passed.
4)
    
{"407917 8774 24",
 "331425 4386 58",
 "502205 9420 32",
 "591461 1548 79",
 "504695 8047 53"}
395439
Returns: 1776

Problem url:

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

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=12008&pm=8608

Writer:

ivan_metelsky

Testers:

PabloGilberto , vorthys , Olexiy

Problem categories:

Simple Search, Iteration, String Parsing