0140. Fidonacci Numbers

Input file name:	fido.in
Output file name:	fido.out
Time limit:	500 ms
Memory limit:	64 megabytes

Fidonacci numbers are defined by conditions F₀=0, F₁=F₂=1 and F_k=F_k-1+F_k-3 for all k ≥ 3. You are to find F_N for a given N.

Input file

One integer number N, 0 ≤ N ≤ 1000.

Output file

Just output the N-th Fidonacci number.

Examples:

fido.in	fido.out
0	0
1	1
2	1

Source: Petrozavodsk Summer 2003. Blitz Kontest, Monday, August 25
Author: Andrew Lopatin, Nick Durov

Discuss       Submit a solution



Printable version