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
Returns: 1
The only possibility here is a perfect circle.
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
Returns: 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.
4
Returns: 5
5
Returns: 6
11
Returns: 39
5
Returns: 6
333
Returns: 7553868
999
Returns: 588025704
1000
Returns: 590382408
333
Returns: 7553868
500
Returns: 37641996
112
Returns: 108680
111
Returns: 104880
445
Returns: 23731875
992
Returns: 571807667
73
Returns: 21463
343
Returns: 8488213
554
Returns: 56512566
460
Returns: 27060033
762
Returns: 200290304
792
Returns: 233512489
405
Returns: 16353966
617
Returns: 86622588
610
Returns: 82792533
879
Returns: 353404464
827
Returns: 277304583
723
Returns: 162551763
839
Returns: 293652240
357
Returns: 9938730
186
Returns: 770816
709
Returns: 150403981
30
Returns: 891
651
Returns: 107172615
209
Returns: 1214010
300
Returns: 5009526
849
Returns: 307818654
418
Returns: 18530645
999
Returns: 588025704
1000
Returns: 590382408