M00PAIR - 0 0 Pairs


A sequence consisting of one digit, the number 1 is initially written into a computer. At each successive time step, the computer simultaneously tranforms 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 consequitive 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 consequitive 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

Notice : Long output - 1.45MB - there are a lot of input/output so it is easy to TLE if you dont optimize in/out if you use Java ...


hide comments
topke: 2015-12-02 17:45:48

Use scanf("%d" , &n) == 1 I've used scanf("%d" , &n) != EOF and got WA

gullu_mishra: 2015-11-03 22:39:00

AC in O(1) time ... simple pattern calculation ;) python rocks

monkz: 2015-09-15 17:04:00

im using vector of ints and getting tle. how should i optimise my code??

The War Machine: 2015-02-14 14:21:37

There may be spaces after each number in input. Be careful while reading the input. It costed me 3 Segmentation faults!

Nevertheless, I enjoyed solving this problem using C++. I wrote BigInteger addition for the first time on my own! It is easy...But I'm happy!! :)

Jugal kishor sahu: 2014-12-17 15:10:09

I did precomputation....but stored in integer array
printing as (one digit)integet- TLE
printing as (one char)char - AC
Learing - printing char is fast than one digit integer :)

vishal johri: 2014-11-26 15:30:43

Found the exact formula for ans: --> :)
Don't know how to output big numbers: --> :(

Last edit: 2014-11-26 15:31:42
Kushal Saharan: 2014-06-09 11:06:37

Use "cin" for taking input and "printf" to output in case you are getting this error SIGXFSZ. #C++

Rishav Goyal: 2014-05-17 17:46:33

try to store results in strings!! @python

Santiago Palacio: 2013-03-29 04:59:22

Ufff.... basic python code will work, but it will barely pass.

Akhil Rao: 2013-01-23 17:18:18

my 100th problem :)


Added by:~!(*(@*!@^&
Date:2009-02-27
Time limit:0.326s
Source limit:20000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ERL JS-RHINO NODEJS PERL6 VB.NET
Resource:Southeastern European 2005