StairwaysToHeaven | Topcoder Archive

Problem Statement

You are standing on the ground floor below a stairway that has n stairs strictly between the ground floor and the top floor. You will climb the stairway using a predetermined strategy, and you must determine the number of steps it will take to get to the top floor.


            +------- top floor
   n=2      |
         +--+ stair 2
         |
      +--+ stair 1
      |
------+ ground floor

Your strategy works as follows: You are given a list of numbers, and you will iterate through that list (wrapping around to the beginning each time you pass the end) until you get to the top floor. A positive number X means that you will take X steps toward the top floor, where each step takes you one stair higher on the stairway. As soon as you take one step higher than the highest stair, you will reach the top floor and immediately stop walking. A negative number -X means that you will take X steps toward the ground floor, where each step takes you one stair lower on the stairway. The constraints guarantee that you will never have to step below the ground floor.

You will be given an int n, the total number of stairs between the two floors, and a int[] strategy, the list of numbers you will use in your strategy. Return the total number of steps required to reach the top floor using the described strategy.

Definition

Class:: StairwaysToHeaven
Method:: countSteps
Parameters:: int[], int
Returns:: long
Method signature:: long countSteps(int[] strategy, int n)
(be sure your method is public)

Constraints

strategy will have between 1 and 50 elements, inclusive.
Each element of strategy will be between -10000000 (-107) and 10000000 (107), inclusive.
The sum of the elements of each proper prefix of strategy will be non-negative.
The sum of all the elements of strategy will be positive.
n will be between 1 and 1000000000 (109), inclusive.

Examples

```
{3,-1}
```
```
5
```
```
Returns: 10
```
In this example, the following will happen: You start at ground level, below the first step, and you take 3 steps up to get to stair 3. Take 1 step down, and you're at stair 2. Take 3 steps up again, and you're at stair 5. Take 1 step down, and you're at stair 4. Take 2 steps up, and you reach your destination (one step up from the 5th stair). Since you are finished, you do not take the extra third step. In total you use 3+1+3+1+2 = 10 steps.
```
{3,-1,3,-1,3,-1}
```
```
5
```
```
Returns: 10
```
This is the same behavior as the previous example, but with a longer strategy.
```
{1}
```
```
9999
```
```
Returns: 10000
```
Just regular climbing.
```
{1,-1,1,-1,1,-1,10000}
```
```
9999
```
```
Returns: 10006
```
Sometimes you want to play a little bit before going up.
```
{1,-1,2,-2,3,-3,4,-4,1}
```
```
9999
```
```
Returns: 209932
```
And sometimes you like to play during the whole trip.

This problem statement is the exclusive and proprietary property of Topcoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of Topcoder, Inc. is strictly prohibited. (c)2024, Topcoder, Inc. All rights reserved.