TopCoder problem "ModelRailroad" used in TCO06 Semi 3 (Division I Level Two)



Problem Statement

    

Your nephew was given a model railroad set as a gift. This railroad set contains pieces of track that can be combined to form a closed loop. There are two types of track: curved pieces, each of which is a 60 degree arc of a circle, and straight pieces. The radius of the arc is three feet, and each straight piece is two feet long.

You have six curved pieces, just enough to make a complete circle, and a given number of straight pieces. Your nephew wants to know how many different track layouts he can construct. Two layouts are considered equivalent if one can be rotated (but not flipped) to be equivalent to the other. Each layout must be a closed loop, with the pieces connected end-to-end. The pieces will only connect in a smooth curve; you cannot connect two pieces at an angle. All possible layouts for five or fewer straight pieces are shown in the figure below:

 

Definition

    
Class:ModelRailroad
Method:countTracks
Parameters:int
Returns:long
Method signature:long countTracks(int straight)
(be sure your method is public)
    
 

Constraints

-straight will be between 0 and 1000, inclusive.
 

Examples

0)
    
0
Returns: 1
The only possibility here is a perfect circle.
1)
    
1
Returns: 1
There is no way to use only one straight track and form a closed loop, so the extra piece is useless.
2)
    
3
Returns: 3
We can either use two straights on opposite sides to make a conventional oval track, or we can use three straights to make a rounded equilateral triangle, or we can make a perfect circle.
3)
    
5
Returns: 6

Problem url:

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

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=9982&pm=6244

Writer:

radeye

Testers:

PabloGilberto , lbackstrom , vorthys , Olexiy , Jan_Kuipers

Problem categories:

Math