Algorithm

Problem link- https://www.spoj.com/problems/IWGBS/

IWGBS - 0110SS

#big-numbers #dynamic-programming

 

Dor is IWGolymp student so he has to count in how many ways he can make N digit numbers that is formed by ones and zeroes. But zeroes can not be next to each other. Help to him in how many different numbers can he make.

For example, N = 3: 101, 010, 111, 110, 011

Note: A leading zero is allowed.

Input

A positive integer N (1 <= N <= 10000).

Output

Answer for the problem.

Example

Input:
2

Output:
3

 

Code Examples

#1 Code Example with Python Programming

Code - Python Programming

N = int(input())
f = [0] * (N + 3)
f[1] = 2
f[2] = 3
for i in range(3, N + 1):
    f[i] = f[i - 2] + f[i - 1]
print(f[N])
Copy The Code & Try With Live Editor

Input

x
–
+
cmd
2

Output

x
–
+
cmd
3
Advertisements

Demonstration

SPOJ Solution-0110SS-Solution in C, C++, Java, Python

Previous
SPOJ Solution - Test Life, the Universe, and Everything - Solution in C, C++, Java, Python