SPOJ #536. How many Fibs

//    536

#include <vector>
#include <iostream>
#include <string>
#include <cmath>
using namespace std;

vector<string> dict;

string plus_str(string &a, string &b)
{
    unsigned sizeA = a.length();
    unsigned sizeB = b.length();
    unsigned sizeDlt = (unsigned)abs(float(sizeA - sizeB));

    string &sL = sizeA > sizeB ? a : b;
    string &sS = !(sizeA > sizeB) ? a : b;


    unsigned sizeL = max(sizeA, sizeB);
    string ret(sizeL + 1, ‘0‘);

    int carry = 0;
    for(int i = sizeL - 1; i >= 0; i --)
    {
        int inxL = i;
        int inxS = i - sizeDlt;
        int inxR = i + 1;

        int dL = sL[inxL] - ‘0‘;
        int dS = inxS < 0 ? 0 : sS[inxS] - ‘0‘;

        int sum = dL + dS + carry;
        ret[inxR] = sum % 10 +‘0‘;
        carry = sum >= 10 ? 1 : 0;
    }

    if(carry)
    {
        ret[0] = ‘1‘;
    }
    else
    {
        ret.erase(0, 1);
    }
    return ret;
}

//    1 : a > b
//    -1: a < b
//    0 : a == b
//
int comp(string &a, string &b)
{
    unsigned sza = a.size();
    unsigned szb = b.size();
    if(sza != szb) return sza > szb ? 1 : -1;

    // the same length
    for(unsigned i = 0; i < sza; i ++)
    {
        int da = a[i] - ‘0‘;
        int db = b[i] - ‘0‘;
        if(da != db)
        {
            return da > db ? 1 : -1;
        }
    }
    return 0;    // equal
}

void fill_fib(vector<string> &dict)
{
    dict.push_back("1");
    dict.push_back("2");

    bool bBreak = false;
    int i = 2;
    while(!bBreak)
    {
        string newFib = plus_str(dict[i - 1], dict[i - 2]);
        dict.push_back(newFib);
        bBreak = newFib.length() >= 101;
        i ++;
    }
}

int get_fib_cnt(string &a, string &b)
{
    int ret = 0;

    unsigned nSize = dict.size();
    for(int i = 0; i <nSize; i ++)
    {
        if(comp(dict[i], b) == 1) break;
        if(comp(dict[i], a) >= 0)
        {
            cout << "Found " << dict[i] << endl;
            ret ++;
        }
    }

    return ret;
}

int main()
{

    fill_fib(dict);

    string a, b;
    cin >> a >> b;

    while(!(a == "0" && b == "0"))
    {
        cout << get_fib_cnt(a, b) << endl;
        cin >> a >> b;
    }

    return 0;
}