PROBLEM STATEMENT
While being stuck in traffic you decide to calculate the speed you need to make
every green light down this street. You know how often the lights turn red and
you want to know how slow you can go, while still not hitting any red lights.
You model the stoplights as follows.
On the x-axis, your car is at x=1. The N lights are at x=3,6,9,...3*N.
At time t=0 all the lights are red, and at t=1 all lights turn from red to
green. Each light has a timing defined by the int[] lights.
For example if a light has a timing of 4, it will be red for 0<=t<1, 4<=t<5,
8<=t<9, 12<=t<13, and in general at time 4*m<=t<4*m+1, for non-negative
integers m. Each light stays red for 1 unit of time before turning green again.
Your goal is to start driving at time t=1 (when all the lights turn green) and
pass all the lights without having to stop. Your task is to calculate the
minimum positive integer constant speed which will allow you to arrive at each
light at a time when the light is green. (Your car can stop on a dime and if a
light turns red at the same time that you arrive at it, you have to stop.
Similarly, if a light turns green at the same instant that you arrive, you
don't have to stop.)
There are no yellow lights and your car is pretty fast, capable of
instantaneous acceleration at time t=1.
The lights are approached in the order they are in the int[] so the first
element is the first light hit.
DEFINITION
Class: StreetLite
Method: neverStop
Parameters: int[]
Returns: int
Method signature (be sure your method is public): int neverStop(int[] lights);
TopCoder will ensure the validity of all inputs. Inputs are valid if:
-lights contains numbers between 2 and 50, inclusive.
-lights contains between 1 and 50 elements, inclusive.
EXAMPLES
1)
lights = {2,7}
We can avoid all the red lights by traveling at a rate of only one unit per
time unit.
We start driving at time t=1
At the t=2 we are at x=2.
At the t=3 we are at x=3 and we hit the first light just as it turns green.
At the t=4 we are at x=4.
At the t=5 we are at x=5.
At the t=6 we are at x=6 and hit the second light, which is still green (it
won't turn red until t=7).
Returns 1
2)
lights = {2,3}
A speed of one doesn't work because we would hit the second light at time 6,
just as it turns red. Neither will 2 because light one will turn red as we get
to it. A speed of three will work though, because we will hit the first light
at time = 1 and 2/3 (it doesn't turn red until time 2) and we will hit the
second light at time = 2 and 2/3 (it doesn't turn red until time = 3)
Returns 3
3)
lights =
{2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2
,2,2,2,2,2,2,2,2,2,2}
returns 150
4) {3,7,6,4,6,9,8,2,6,5,10,3,8,5,2,7,33,26,16,27,37}
returns 11