## UCC Coding Competition '21 P4 - Trampoline Jump

View as PDF

Points: 7 (partial)
Time limit: 2.0s
Memory limit: 256M

Author:
Problem type

The Fibonacci Sequence is a mathematical sequence where the first and second terms are 1, and each term after that is the sum of the two previous terms. More formally, if denotes the term of the Fibonacci Sequence, then , and for all integer .

The modulo (or ) operation is an operation represented by the symbol. The expression denotes the remainder when the positive integer is divided by the positive integer . For example, , because the remainder when is divided by is . The modulo operator is available in most programming languages using the operator % - for example, the line int a = 7%2; in C++ will set a to be 1.

You have found yourself at the first house of a long street. There are a total of houses along this street, numbered to . You are trying to travel from the first house to the last house as fast as possible.

You can always walk from one house to an adjacent house (i.e. from house to house or house , if they exist). This takes one minute.

At each house, there is also a trampoline that allows you to travel a larger distance. In particular, at the house, there is a trampoline with strength . Using the trampoline also takes one minute, and from house , you can use the trampoline to jump either backwards to house (as long as ) or forwards to house (as long as ).

You have been able to reverse-engineer a pattern of the values of for all the houses:

for all ,

where represents the term in the Fibonacci Sequence and represents the modulo operation, as defined at the beginning of the problem.

For reference purposes, , , , , , , , and .

Please find the minimum number of minutes you need to travel from house to house .

NOTE FOR PYTHON USERS: If your program receives TLE (time limit exceeded), you should try submitting using the PyPy interpreter: when you are submitting your code, try using "PyPy 3" or "PyPy 2" as the language, instead of "Python 3" or "Python 2".

#### Input Specification

The input will consist of one integer, , the number of houses on the street.

#### Output Specification

Please output the minimum number of minutes you need to travel from house to house .

#### Constraints and Partial Marks

For of the available marks, .

For the remaining marks, .

#### Sample Input 1

9

#### Sample Output 1

3

#### Explanation for Sample Output 1

The first terms of the sequence are . To travel from house to house , the optimal pattern of moves is:

• Move : Jump from house to house . This is possible as .
• Move : Jump from house to house . This is possible as .
• Move : Walk from house to house . This is possible as .

Every move takes minute, so the output is 3.

#### Sample Input 2

27

#### Sample Output 2

4

#### Explanation for Sample Output 2

One way to reach house in moves is as follows:

• Move : Jump from house to house . This is possible as .
• Move : Jump from house to house . This is possible as .
• Move : Walk backwards from house to house . This is possible as .
• Move : Jump from house to house . This is possible as .