TopCoder problem "Stairs" used in SRM 177 (Division II Level One)



Problem Statement

    A set of stairs consists of risers (the vertical parts of the stairs) and treads (the horizontal parts that you walk on). The stairs alternate treads and risers, starting and ending with a riser as shown below.

A set of stairs with two treads would have three risers and would look similar to this picture:


                +........
                |
            +---+
            |
        +---+
        |
........+

We have the following requirements for a set of stairs:

  1. all risers must have the same integer height
  2. all treads must have the same integer width
  3. each riser must be less than or equal to maxHeight
  4. each tread must be greater than or equal to minWidth
The totalWidth of the stairs is the sum of all the tread widths, while the totalHeight of the stairs is the sum of all the riser heights. The stairs start with a riser and end with a riser.

Create a class Stairs that contains a method designs that takes as input four ints: maxHeight, minWidth, totalHeight, totalWidth. It returns the number of different designs that meet the design criteria.

 

Definition

    
Class:Stairs
Method:designs
Parameters:int, int, int, int
Returns:int
Method signature:int designs(int maxHeight, int minWidth, int totalHeight, int totalWidth)
(be sure your method is public)
    
 

Constraints

-maxHeight, minWidth, totalHeight, and totalWidth will be between 1 and 1000 inclusive
 

Examples

0)
    
22
25
100
100
Returns: 1
The only design is to have each riser be 20, each tread be 25.
1)
    
25
25
60
100
Returns: 2
We could have riser height 12 with tread width 25, or we could have riser height 20, tread width 50. The design with just one tread of width 100 would force each riser to be 30 which exceeds the specified maxHeight, and a design with 6 risers of height 10 would result in treads of width 20 which is smaller than the specified minWidth.
2)
    
1000
1
600
600
Returns: 6
There are six different designs. The one with the biggest steps has just one tread of size 600, and two risers of size 300. The one with the smallest steps has 24 treads, each of width 25, and its 25 risers each have a height of 24.

Problem url:

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

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=4690&pm=2011

Writer:

dgoodman

Testers:

lbackstrom , brett1479

Problem categories:

Brute Force