ENG  RUS Timus Online Judge
Online Judge
Problems
Authors
Online contests
Site news
Webboard
Problem set
Submit solution
Judge status
Guide
Register
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules
back to board

## Discussion of Problem 1462. Uncle Scrooge's Gold

How to more optimize~Code here...Thank you!!!
Posted by Search 25 Sep 2008 01:10
#include <cstdio>
#include <string>
#include <memory>
using namespace std;

class BigInteger{
private:
enum{MAXLENGTH=14900};
int m[MAXLENGTH];
int len;

public:
BigInteger(int n)
{
memset(m,0,sizeof(m));
len=0;
if (n == 0) len++;
while (n > 0)
{
m[len++] = n % 10;
n = n / 10;
}
}

BigInteger(void)
{
memset(m,0,sizeof(m));
len=1;
}

void print(void)
{
int temp = len-1;
while(temp>=0) printf("%d",m[temp--]);
}

BigInteger operator+ (const BigInteger &a)
{
int i,carry = 0;
BigInteger Temp(*this);
if (a.len > Temp.len) Temp.len = a.len;
for(i=0;i<Temp.len;i++)
{
Temp.m[i] += (a.m[i] + carry);
carry =  Temp.m[i] / 10;
Temp.m[i] %= 10;
}
if (carry > 0) {Temp.m[i] = carry; Temp.len++;}
return Temp;
}

int operator> (const BigInteger &a)
{
int i;
if (len > a.len) return 1;
if (len < a.len) return 0;
for(i=len-1;(m[i] == a.m[i]) && (i>0);i--);
if (m[i] > a.m[i]) return 1;
return 0;
}
int operator== (const BigInteger &a)
{
int i;
if (len != a.len) return 0;
for(i = len-1;i>=0;i--)
if (m[i] != a.m[i]) return 0;
return 1;
}

};
int main()
{
int n;

scanf("%d",&n);
BigInteger r1;int i;
BigInteger previous = -1;
BigInteger result = 1;
for (i = 0; i<n; i++)
{
BigInteger const sum = result + previous;
previous = result;
result = sum;
if(i==n-3){
r1=result;
}
}
(r1+result).print();
return 0;
}

Edited by author 25.09.2008 01:10
Re: How to more optimize~Code here...Thank you!!!
Posted by 3a[3.141592..]Jlu 18 Mar 2009 14:59
Use long ariphmetics on base 10^9 or 10^18, but not 10^1 :)