POJ.2413 How many Fibs?

1.Problem
http://poj.org/problem?id=2413

2.Idea
Enumerating first 500 fibs numbers.

3.Source

 string add(string a, string b)  
 {  
      if (a == "") return b;  
      if (b == "") return a;  
      if (a.length() < b.length()) swap(a, b);  
      int d = a.length() - b.length();  
      for (int i = 0; i < d; i++) {  
           b = "0" + b;  
      }  
      int car = 0;  
      int n = a.length();  
      for (int i = n - 1; i >= 0; i--) {  
           int tmp = car + a[i] + b[i] - '0' - '0';  
           a[i] = '0' + (tmp % 10);  
           car = tmp / 10;  
      }  
      if (car > 0) return "1" + a;  
      else return a;  
 }  
 bool isNotSmaller(string a, string b) // a <= b -> true  
 {  
      if (a == b) return true;  
      if (a.length() < b.length()) return true;  
      if (a.length() == b.length() && a <= b) return true;  
      return false;  
 }  
 bool isNotGreater(string a, string b) // a >= b -> true  
 {  
      if (a == b) return true;  
      if (a.length() > b.length()) return true;  
      if (a.length() == b.length() && a >= b) return true;  
      return false;  
 }  
 vector<string> fibs;  
 int main()  
 {  
      fibs.push_back("1");  
      fibs.push_back("1");  
      for (int i = 2; i < 500; i++) {  
           string tmp = add(fibs[i - 1], fibs[i - 2]);  
           fibs.push_back(tmp);  
      }  
      while (true) {  
           string a, b;  
           cin >> a >> b;  
           if (a == "0" && b == "0") break;  
           int cnt = 0;  
           for (int i = 1; i < 500; i++) {  
                if (isNotSmaller(a, fibs[i]) && isNotGreater(b, fibs[i])) cnt++;  
           }  
           cout << cnt << endl;  
      }  
      return 0;  
 }  

POJ.2506 Tiling

1.Problem
http://poj.org/problem?id=2506

2.Idea
DP+BigInt Lib
3.Source

 const int Base = 1000000000;  
 const int Capacity = 100;  
 typedef long long huge;  
 struct BigInt {  
      int Len;  
      int Data[Capacity];  
      BigInt() : Len(0) {}  
      BigInt(const BigInt &V) : Len(V.Len) { memcpy(Data, V.Data, Len * sizeof*Data); }  
      BigInt(int V) : Len(0) { for (; V>0; V /= Base) Data[Len++] = V%Base; }  
      BigInt &operator=(const BigInt &V) { Len = V.Len; memcpy(Data, V.Data, Len * sizeof*Data); return *this; }  
      int &operator[] (int Index) { return Data[Index]; }  
      int operator[] (int Index) const { return Data[Index]; }  
 };  
 int compare(const BigInt &A, const BigInt &B) {  
      if (A.Len != B.Len) return A.Len>B.Len ? 1 : -1;  
      int i;  
      for (i = A.Len - 1; i >= 0 && A[i] == B[i]; i--);  
      if (i<0)return 0;  
      return A[i]>B[i] ? 1 : -1;  
 }  
 BigInt operator+(const BigInt &A, const BigInt &B) {  
      int i, Carry(0);  
      BigInt R;  
      for (i = 0; i<A.Len || i<B.Len || Carry>0; i++) {  
           if (i<A.Len) Carry += A[i];  
           if (i<B.Len) Carry += B[i];  
           R[i] = Carry%Base;  
           Carry /= Base;  
      }  
      R.Len = i;  
      return R;  
 }  
 BigInt operator-(const BigInt &A, const BigInt &B) {  
      int i, Carry(0);  
      BigInt R;  
      R.Len = A.Len;  
      for (i = 0; i<R.Len; i++) {  
           R[i] = A[i] - Carry;  
           if (i<B.Len) R[i] -= B[i];  
           if (R[i]<0) Carry = 1, R[i] += Base;  
           else Carry = 0;  
      }  
      while (R.Len>0 && R[R.Len - 1] == 0) R.Len--;  
      return R;  
 }  
 BigInt operator*(const BigInt &A, const int &B) {  
      int i;  
      huge Carry(0);  
      BigInt R;  
      for (i = 0; i<A.Len || Carry>0; i++) {  
           if (i<A.Len) Carry += huge(A[i])*B;  
           R[i] = Carry%Base;  
           Carry /= Base;  
      }  
      R.Len = i;  
      return R;  
 }  
 istream &operator >> (istream &In, BigInt &V) {  
      char Ch;  
      for (V = 0; In >> Ch;) {  
           V = V * 10 + (Ch - '0');  
           if (In.peek() <= ' ') break;  
      }  
      return In;  
 }  
 ostream &operator<<(ostream &Out, const BigInt &V) {  
      int i;  
      Out << (V.Len == 0 ? 0 : V[V.Len - 1]);  
      for (i = V.Len - 2; i >= 0; i--) for (int j = Base / 10; j>0; j /= 10) Out << V[i] / j % 10;  
      return Out;  
 }  
 #define MAXN 250  
 BigInt dp[MAXN + 5];  
 int main()  
 {  
      memset(dp, 0, sizeof(dp));  
      dp[0] = 1;  
      dp[1] = 1;  
      dp[2] = 3;  
      dp[3] = 5;  
      for (int i = 4; i <= MAXN; i++) {  
           dp[i] = dp[i - 2] * 2 + dp[i - 1];  
      }  
      int t;  
      while (scanf("%d", &t) != EOF)  
           cout << dp[t] << endl;  
      return 0;  
 }