Connection Status:
Competition Arena > BusAwaiting

BusAwaiting

TCO08 Qual 2 · 2008-01-21 · by ivan_metelsky

TCO08 Qual 2 · 2008-01-21 · by ivan_metelsky · Simple Search, Iteration, String Parsing
Class Name: BusAwaiting
Return Type: int
Method Name: waitingTime
Arg Types: (vector<string>, int)
Problem Statement

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.

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

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

Coding Area

Language: C++17 · define a public class BusAwaiting with a public method int waitingTime(vector<string> buses, int arrivalTime) · 172 test cases · 2 s / 256 MB per case

Submitting as anonymous