UVA 10862 Connect the Cable Wires

#include<bits/stdc++.h>
using namespace std;

typedef long long           ll;
typedef unsigned long long  ull;
typedef double              ld;//%Lf
#define ff                  first
#define ss                  second
#define pb                  push_back
#define mp                  make_pair
#define ppb                 pop_back
#define in                  insert
#define sz(a)               int((a).size())
#define vi                  vector<int>
#define vl                  vector<ll>
#define vvi                 vector<vector<int> >
#define pii                 pair<int,int>
#define piii                pair<int,pair<int,int> >
#define pll                 pair<ll,ll>
#define vii                 vector<pii>
#define vll                 vector<pll>
#define viii                vector<piii>
#define YES                 cout << "YES\n"
#define NO                  cout << "NO\n"

#define scl(n)              scanf("%lld",&n)
#define scll(x,y)           scanf("%lld %lld",&x,&y)
#define gtl(x)              getline(cin, (x))

#define f0(b)               for(int i=0;i<(b);i++)
#define f00(b)              for(int j=0;j<(b);j++)
#define f1(b)               for(int i=1;i<=(b);i++)
#define f11(b)              for(int j=1;j<=(b);j++)
#define f2(a,b)             for(int i=(a);i<=(b);i++)
#define f22(a,b)            for(int j=(a);j<=(b);j++)
#define RFOR(i,x,y)         for(int i=x;i>=y;i--)
#define all(v)              v.begin(),v.end()
#define rall(v)             v.rbegin(),v.rend()
#define unq(v)              sort(all(v)),(v).resize(unique(all(v))-v.begin())
#define present(c,x)        ((c).find(x) != (c).end())
#define cpresent(c,x)       (find(all(c),x) != (c).end())
#define min_ele(v)          (*min_element(all(v)))
#define max_ele(v)          (*max_element(all(v)))
#define cnt_ele(v, x)       (count(all(v), x))
#define sum_ele(v)          (accumulate(all(v),0))
#define reversed(s)         reverse(s.begin(), s.end())

#define testcase            ll t; cin>>t; while (t--)
#define vout(v)             for(int ind=0;ind<v.size();ind++){ cout<<v[ind]; if(ind<v.size()-1) cout<<' '; else cout<<endl;}
#define arrout(arr,i,x,y)   for(int i=x;i<=y;i++){ cout<<arr[i]; if(i<y) cout<<' '; else cout<<endl;}
#define PI                  acos(-1)
#define CLR(x, y)           memset(x, y, sizeof(x))
#define Precision(a)        cout << fixed << setprecision(a)
#define BITCH_FAST()        ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0) //Don't use scanf/printf
#define MAXP                100006
#define INF9                2147483647
#define INF18               9223372036854775806
#define MOD                 1e9+7//10000007 // For big mod
#define EPS                 1e-7

template <typename T> T Sqr(T x) { T n = x * x ; return n ;}
template <typename T> T Pow(T B,T P){ if(P==0) return 1; if(P&1) return B*Pow(B,P-1);  else return Sqr(Pow(B,P/2));}
template <typename T> T Abs(T a) {if(a<0)return -a;else return a;}
template <typename T> T Gcd(T a,T b){if(a<0)return Gcd(-a,b);if(b<0)return Gcd(a,-b);return (b==0)?a:Gcd(b,a%b);} // better than __gcd
template <typename T> T Lcm(T a,T b) {if(a<0)return Lcm(-a,b);if(b<0)return Lcm(a,-b);return a*(b/Gcd(a,b));}
template <typename T> T power(T n, T p){ T res = 1;while(p > 0){if(p & 1)res *= n;n *= n;p >>= 1;}return res;}
template <typename T> T BigMod (T b,T p,T m){if (p == 0) return 1;if (p%2 == 0){T s = BigMod(b,p/2,m);return ((s%m)*(s%m))%m;}return ((b%m)*(BigMod(b,p-1,m)%m))%m;}
template <typename T> inline string ToBinary(T n) {string r ;while(n != 0) {r = ( n % 2 == 0 ? "0" : "1" ) + r ; n >>= 1;} return r ;}
long long BinaryToDecimal(string s) {int len = s.size();long long n = 0, p = 1;for (int i = len - 1; i >= 0; i-- , p *= 2) n += p * (s[i] - '0');return n;}
int Strtoint(string str){stringstream ss(str);int x = 0;ss >> x ;return x ;}
string Intostr(int x){stringstream ss; ss << x; string str = ss.str(); return str;}

/*----------------------Graph Moves----------------*/
int ROW[]={+1,-1,+0,+0};
int COL[]={+0,+0,+1,-1};

int X[]={+0,+0,+1,-1,-1,+1,-1,+1};   // Kings Move
int Y[]={-1,+1,+0,+0,+1,+1,-1,-1};  // Kings Move

int KX[]={-2, -2, -1, -1,  1,  1,  2,  2};  // Knights Move
int KY[]={-1,  1, -2,  2, -2,  2, -1,  1}; // Knights Move

string fib[MAXP];
string Add_sum(string str1,string str2)
{

    if (str1.length() > str2.length())
        swap(str1, str2);


    int n1 = str1.length(), n2 = str2.length();
    string str = "";

    reverse(str1.begin(), str1.end());
    reverse(str2.begin(), str2.end());
    ll carry = 0;
    for (int i=0; i<n1; i++)
    {
        // Do school mathematics, compute sum of
        // current digits and carry
        int sum = ((str1[i]-'0')+(str2[i]-'0')+carry);
        str.push_back(sum%10 + '0');

        // Calculate carry for next step
        carry = sum/10;
    }

    // Add remaining digits of larger number
    for (int i=n1; i<n2; i++)
    {
        int sum = ((str2[i]-'0')+carry);
        str.push_back(sum%10 + '0');
        carry = sum/10;
    }

    // Add remaining carry
    if (carry)
        str.push_back(carry+'0');

    // reverse resultant string
    reverse(str.begin(), str.end());

    return str;
}

void Fibs()
{
    fib[0]="0";
    fib[1]="1";
    for(ll i=2; i<=4005; i++)
    {
        fib[i]=Add_sum(fib[i-1], fib[i-2]);
    }
}

int main()
{
    BITCH_FAST();
    #ifdef FLAME
        clock_t tStart = clock();
        freopen("input.txt", "r", stdin);
        freopen("output.txt", "w", stdout);
    #endif
    Fibs();
    ll n;
    while(cin >> n && n)
    {
        cout<< fib[n*2] << endl;
    }

    #ifdef FLAME
        fprintf(stderr, "\n>> Runtime: %.10fs\n", (double) (clock() - tStart) / CLOCKS_PER_SEC);
    #endif
    return 0;
}