#include <iostream>
using namespace std;
// compute fibonacci number for a given n>=0
int fibonacci(int n)
{
int f, f1, f2;
// for 0 and 1, just return the result right away
if (n==0)
return 0;
if (n==1)
return 1;
// f1 and f2 store the previous two fibonacci numbers
// initialized to f1=0, and f2=1 (for fib0 and fib1).
f1 = 0;
f2 = 1;
// compute the next fibonacci number until we get
// to the target one
for (int i=2; i<=n; i++)
{
// compute new fibonacci number
f = f1 + f2;
// move previous to one before the previous
// and move current into previous, for the next
// iteration (we are going to generate a new
// number)
f1 = f2;
f2 = f;
}
return f;
}
// main function
int main()
{
int n;
// read n from the user
cin >> n;
// compute and output the fibonacci number f(n)
cout << "fib(" << n << ") = " << fibonacci(n) << endl;
// return from main
return 0;
}
I2luY2x1ZGUgPGlvc3RyZWFtPgoKdXNpbmcgbmFtZXNwYWNlIHN0ZDsKCi8vIGNvbXB1dGUgZmlib25hY2NpIG51bWJlciBmb3IgYSBnaXZlbiBuPj0wCgppbnQgZmlib25hY2NpKGludCBuKQp7CiAgaW50IGYsIGYxLCBmMjsKCiAgLy8gZm9yIDAgYW5kIDEsIGp1c3QgcmV0dXJuIHRoZSByZXN1bHQgcmlnaHQgYXdheQoKICBpZiAobj09MCkKICAgIHJldHVybiAwOwoKICBpZiAobj09MSkKICAgIHJldHVybiAxOwoKICAvLyBmMSBhbmQgZjIgc3RvcmUgdGhlIHByZXZpb3VzIHR3byBmaWJvbmFjY2kgbnVtYmVycwogIC8vIGluaXRpYWxpemVkIHRvIGYxPTAsIGFuZCBmMj0xIChmb3IgZmliMCBhbmQgZmliMSkuCiAgCiAgZjEgPSAwOwogIGYyID0gMTsKCiAgLy8gY29tcHV0ZSB0aGUgbmV4dCBmaWJvbmFjY2kgbnVtYmVyIHVudGlsIHdlIGdldAogIC8vIHRvIHRoZSB0YXJnZXQgb25lCgogIGZvciAoaW50IGk9MjsgaTw9bjsgaSsrKQogICAgewogICAgICAvLyBjb21wdXRlIG5ldyBmaWJvbmFjY2kgbnVtYmVyCiAgICAgIGYgPSBmMSArIGYyOyAKCiAgICAgIC8vIG1vdmUgcHJldmlvdXMgdG8gb25lIGJlZm9yZSB0aGUgcHJldmlvdXMKICAgICAgLy8gYW5kIG1vdmUgY3VycmVudCBpbnRvIHByZXZpb3VzLCBmb3IgdGhlIG5leHQKICAgICAgLy8gaXRlcmF0aW9uICh3ZSBhcmUgZ29pbmcgdG8gZ2VuZXJhdGUgYSBuZXcgCiAgICAgIC8vIG51bWJlcikKCiAgICAgIGYxID0gZjI7CiAgICAgIGYyID0gZjsKICAgIH0KCiAgcmV0dXJuIGY7Cn0KCi8vIG1haW4gZnVuY3Rpb24KCmludCBtYWluKCkKewogIGludCBuOwoKICAvLyByZWFkIG4gZnJvbSB0aGUgdXNlcgoKICBjaW4gPj4gbjsKCiAgLy8gY29tcHV0ZSBhbmQgb3V0cHV0IHRoZSBmaWJvbmFjY2kgbnVtYmVyIGYobikKCiAgY291dCA8PCAiZmliKCIgPDwgbiA8PCAiKSA9ICIgPDwgZmlib25hY2NpKG4pIDw8IGVuZGw7CgogIC8vIHJldHVybiBmcm9tIG1haW4KCiAgcmV0dXJuIDA7Cn0=