[UVa] 12333 - Revenge of Fibonacci

Author            : Dipu Kumar Mohanto 
                    CSE, Batch - 6
                    BRUR.
Problem Statement : 12333 - Revenge of Fibonacci
Source            : UVA Online Judge
Category          : Large Fibonacci Number
Algorithm         : Trie
Verdict           : Accepted

#include "bits/stdc++.h"  
  
using namespace std;  
  
#define sz(a)            (int)a.size()  
  
struct Trie  
{  
      int endd;  
      Trie *child[10];  
      Trie()  
      {  
            endd = -1;  
            for (int i = 0; i < 10; i++) child[i] = nullptr;  
      }  
      ~Trie()  
      {  
            for (int i = 0; i < 10; i++)  
            {  
                  if (child[i] && child[i] != this) delete child[i];  
            }  
      }  
};  
  
typedef Trie*         pnode;  
  
pnode root;  
  
inline void Insert(const string &s, int fibo)  
{  
      pnode cur = root;  
      int len = sz(s);  
      for (int i = 0; i < min(len, 43); i++)  
      {  
            int val = s[i] - '0';  
            if (cur->child[val] == nullptr) cur->child[val] = new Trie();  
            cur = cur->child[val];  
            if (cur->endd == -1) cur->endd = fibo;  
      }  
}  
  
inline int Search(const string &s)  
{  
      pnode cur = root;  
      int len = sz(s);  
      for (int i = 0; i < len; i++)  
      {  
            int val = s[i] - '0';  
            if (cur->child[val] == nullptr) return -1;  
            cur = cur->child[val];  
      }  
      return cur->endd;  
}  
  
inline int toInt(char ch)  
{  
      return (int)(ch - '0');  
}  
  
inline string add(string a, string b)  
{  
      while (sz(a) < sz(b)) a = "0" + a;  
      while (sz(b) < sz(a)) b = "0" + b;  
      string res = "";  
      int carry = 0;  
      for (int i = sz(a) - 1; i >= 0; i--)  
      {  
            int sum = toInt(a[i]) + toInt(b[i]) + carry;  
            carry = 0;  
            if (sum > 9)  
            {  
                  carry++;  
                  sum -= 10;  
                  res += (char)(sum + '0');  
            }  
            else  
            {  
                  res += (char)(sum + '0');  
            }  
      }  
      if (carry) res += "1";  
      reverse(res.begin(), res.end());  
      while (*res.begin() == '0') res.erase(res.begin());  
      return res;  
}  
  
inline void fibo_calc()  
{  
      string a = "1";  
      string b = "1";  
      Insert(a, 0);  
      for (int i = 2; i < 100000; i++)  
      {  
            string fn = add(a, b);  
            Insert(fn, i);  
            a = b;  
            b = fn;  
      }  
}  
  
  
int main()  
{  
      ios_base::sync_with_stdio(false);  
      cin.tie(nullptr);  
  
      root = new Trie();  
      fibo_calc();  
      int tc;  
      cin >> tc;  
      for (int tcase = 1; tcase <= tc; tcase++)  
      {  
            string s;  
            cin >> s;  
            cout << "Case #" << tcase << ": " << Search(s) << endl;  
      }  
}