Algorithm

problem link- https://www.spoj.com/problems/M00PAIR/

M00PAIR - 0 0 Pairs

#dynamic-programming

 

 

English Vietnamese

 

A sequence consisting of one digit, the number 1 is initially written into a computer. At each successive time step, the computer simultaneously transforms each digit 0 into the sequence 1 0 and each digit 1 into the sequence 0 1.

So, after the first time step, the sequence 0 1 is obtained; after the second, the sequence 1 0 0 1, after the third, the sequence 0 1 1 0 1 0 0 1 and so on.

How many pairs of consecutive zeroes will appear in the sequence after n steps?

Input

Clarification for this Problem: The Range of inputs is from 1 to 999 in some order and in particular not in ascending order

Output

For each input n print the number of consecutive zeroes pairs that will appear in the sequence after n steps.

Sample

Sample Input 
1
2 
3 
4
5 

Sample output 
0
1 
1
3
5

 

Code Examples

#1 Code Example with Python Programming

Code - Python Programming

dp = [0] * 1005
dp[1] = 0
dp[2] = 1
for i in range(3, 1005):
    dp[i] = dp[i - 1] + 2 * dp[i - 2]
while True:
    try:
        N = int(input())
        print(dp[N])
    except EOFError:
        exit()
Copy The Code & Try With Live Editor

Input

x
–
+
cmd
1
2
3
4
5

Output

x
–
+
cmd
0
1
1
3
5
Advertisements

Demonstration

SPOJ Solutioon-M00PAIR 0 0 Pairs-Solution in C, C++, Java, Python

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