#include <stdio.h>
int fib1(int n)
{
int f0=0,f1=1,fn=0,count=2;
while(count<=n)
{
fn=f0+f1;
f0=f1;
f1=fn;
count++;
}
return fn;
}
int fib2(int n) {
int f[50];
f[0]=0;
f[1]=1;
for(int i=2;i<=n;i++)
{
f[i]=f[i-1]+f[i-2];
}
return f[n];
}
int fib3(int n)
{
if(n==0)
return 0;
else if(n==1)
return 1;
else
return fib3(n-1)+fib3(n-2);
}
int fib_memo(int n)
{
static int memo[50];
if(n==0)
return 0;
else if(n==1)
return 1;
else
{
if(memo[n]!=0)
return memo[n];
else
return memo[n]=fib3(n-1)+fib3(n-2);
}
}
int main(void)
{
int n;
return 0;
}
I2luY2x1ZGUgPHN0ZGlvLmg+CgppbnQgZmliMShpbnQgbikgCnsKIGludCBmMD0wLGYxPTEsZm49MCxjb3VudD0yOyAKIAogd2hpbGUoY291bnQ8PW4pCiB7CiAgZm49ZjArZjE7IAogIGYwPWYxOyAKICBmMT1mbjsgCiAgY291bnQrKzsgCiB9CiByZXR1cm4gZm47IAp9CgppbnQgZmliMihpbnQgbikgewogaW50IGZbNTBdOyAKIAogZlswXT0wOyAKIGZbMV09MTsgCiAKIGZvcihpbnQgaT0yO2k8PW47aSsrKSAKIHsKICBmW2ldPWZbaS0xXStmW2ktMl07IAogfQogcmV0dXJuIGZbbl07IAp9CgppbnQgZmliMyhpbnQgbikgCnsKIGlmKG49PTApIAogIHJldHVybiAwOyAKIGVsc2UgaWYobj09MSkgCiAgcmV0dXJuIDE7IAogZWxzZSAKICByZXR1cm4gZmliMyhuLTEpK2ZpYjMobi0yKTsgCn0KCmludCBmaWJfbWVtbyhpbnQgbikgCnsKIHN0YXRpYyBpbnQgbWVtb1s1MF07IAogCiBpZihuPT0wKSAKICByZXR1cm4gMDsgCiBlbHNlIGlmKG49PTEpIAogIHJldHVybiAxOyAKIGVsc2UgCiB7CiAgaWYobWVtb1tuXSE9MCkgCiAgIHJldHVybiBtZW1vW25dOyAKICBlbHNlIAogICByZXR1cm4gbWVtb1tuXT1maWIzKG4tMSkrZmliMyhuLTIpOyAKIH0KICAKfQoKaW50IG1haW4odm9pZCkKewogaW50IG47IAogCiBzY2FuZigiJWQiLCZuKTsgCiAKIHByaW50ZigiMTolZFxuIixmaWIxKG4pKTsgCiBwcmludGYoIjI6JWRcbiIsZmliMihuKSk7IAogcHJpbnRmKCIzOiVkXG4iLGZpYjMobikpOyAKIHByaW50ZigiNDolZFxuIixmaWJfbWVtbyhuKSk7IAogCiByZXR1cm4gMDsKfQ==