Codesignal Solution: monkeyBars
You are at the International Monkey Bars Climbing Competition 2017
! Each contestant must climb various stretches of monkey bars during each round. The rules are that you may not more move than 3
bars at a time. Find the number of distinct ways to climb a given section.
Example
For n = 4
, the output should bemonkeyBars(n) = 7
.
There are 7
distinct ways to climb the bars - 3 + 1, 1 + 3, 2 + 1 + 1, 1 + 2 + 1, 1 + 1 + 2, 1 + 1 + 1 + 1, 2 + 2
.
Input/Output
- [time limit] 4000ms (py3)
-
[input] integer n
Number of bars.
Guaranteed constraints:
1 ≤ n ≤ 60
. -
[output] integer64
Number of distinct ways to climb.
Solution
When investigating the series, we can see that the emerging pattern is known as the tribonacci number sequence - a generalization of fibonacci numbers. The definition is
\[T_n = T_{n-1} + T_{n-2} + T_{n-3}\]
for \(n\geq 4\) and \(T_1=T_2=1, T_3=2\). This recurrence relation can be implemented with Python like this:
def monkeyBars(n): a = b = 1 c = 2 while n: a, b, c = b, c, a + b + c n-= 1 return a