Submit solution
Points:
15 (partial)
Time limit:
1.0s
Memory limit:
64M
Problem type
Allowed languages
Ada, Assembly, Awk, Brain****, C, C#, C++, COBOL, CommonLisp, D, Dart, F#, Forth, Fortran, Go, Groovy, Haskell, Intercal, Java, JS, Kotlin, Lisp, Lua, Nim, ObjC, OCaml, Octave, Pascal, Perl, PHP, Pike, Prolog, Python, Racket, Ruby, Rust, Scala, Scheme, Sed, Swift, TCL, Text, Turing, VB, Zig
The Fibonacci sequence is a well known sequence of numbers in which
Given a number
, find the
Fibonacci number, modulo
.
Note: For 30% of the marks of this problem, it is guaranteed that .
Input Specification
The first line of input will have the number .
Output Specification
The Fibonacci number, modulo
.
Sample Input
26
Sample Output
121393
Comments
Any ideas on how to cut down on the recursive calls and avoid a stack overflow on the last case?
Edit: Avoid MLE
If im reading your code, you are reading in a long while the max value is above a long. Avoid using a long for input.
What should I use for input then?
You can read the input using unsigned long long.
Ah, it worked, thanks!
For some reason, my code doesn't work on this platform but it does on every other platform and all my test cases are right.
You should try testing your code with large test cases. For example,
.
The 10^19 overflowed my scanf need to use scanf("%llu",&n);
In C++ if you're using map for memoization for example F[n] = fib(n-1)+fib(n-2) then F[n] may be created before the fib(n-1)+fib(n-2) returns a value, so better use something like a = fib(n-1)+fib(n-2); then F[n] = a;
This comment is hidden due to too much negative feedback. Click here to view it.
This comment is hidden due to too much negative feedback. Click here to view it.
The intended solution uses matrices which is considered advanced math for DMOJ tags.
This comment is hidden due to too much negative feedback. Click here to view it.
r3mark hijacked global smurf cuz he submiited some 15+ pointers on it.
This submission was submitted in December 2015. https://dmoj.ca/submission/25109 https://gyazo.com/384dbe04e5e09316b99739e7eb9497ca
Edit: Fixed, timestamp now says 2014.
This comment is hidden due to too much negative feedback. Click here to view it.
This is not a recursive problem.
https://www.ics.uci.edu/~eppstein/161/960109.html
The problem requires you to output mod
. That means that you need to get the remainder of the final answer when it is divided by
. This operation can be done in Python, C++, and Java by using '%'.
It may interest you to know that
is a prime number.
There are a two highly useful properties of modular arithmetic we often use in programming competitions (% has the same precedence as multiplication and division):
This problem is a lot more difficult than it may appear. There is a reason for 15 points. The input can be as big as
.
This comment is hidden due to too much negative feedback. Click here to view it.
The typical dynamic programming solution will not pass the larger inputs. More math insights is used in the solution rather than dynamic programming.