Cod sursa(job #124081)

Utilizator devilkindSavin Tiberiu devilkind Data 18 ianuarie 2008 00:39:02
Problema Sarpe Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.38 kb
#include <stdio.h>
#include <vector>
#include <algorithm>

using namespace std;

#define NMAX 1002
#define pb push_back
#define sz size()

vector<int> v,sol,v1,v2,aux;
long int i,j,k;
char s[NMAX];

vector<int> add(vector<int> t1, vector<int> t2)
{
int t=0,i,x;
vector<int> rez;

vector<int>().swap(rez);

for (i=0;(i<t1.sz)||(i<t2.sz)||(t);i++)
        {
        if (i<t1.sz) t=t+t1[i];
        if (i<t2.sz) t=t+t2[i];
        rez.pb(t%10);
        t/=10;
        }
        
return rez;
}

vector<int> mult(vector<int> t1, vector<int> t2)
{

long int t=0,i,j;
vector<int> rez;
rez.clear();

for (i=0;i<t1.sz;i++)
        for (t=0,j=0;(j<t2.sz)||(t);j++)
                {
                if (j<t2.sz) t=t+t1[i]*t2[j];
                
                if (rez.sz<=i+j) rez.pb(0);

                t=t+rez[i+j];
                rez[i+j]=t%10;
                t/=10;
                }
return rez;
}


int main()
{
freopen("sarpe.in","r",stdin);
freopen("sarpe.out","w",stdout);

fgets(s,NMAX,stdin);

for (i=0;s[i]>='0'&&s[i]<='9';i++)
        v.pb(s[i] - '0');
reverse(v.begin(),v.end());

if ( (v.sz==1)&&(v[0]==1) ) {printf("2\n");return 0;}

v1.pb(4);
sol=mult(v1,v);

v1=v;
v1[0]--;
for (i=0;v1[i]==-1;i++) {v1[i]=9;v1[i+1]--;}

v2=v1;
v2[0]--;
for (i=0;v2[i]==-1;i++) {v2[i]=9;v2[i+1]--;}

v=mult(v1,v2);
v1.clear();v1.pb(2);
sol=add(sol, mult(v,v1) );
for (i=sol.sz-1;i>=0;i--) printf("%ld",sol[i]);
return 0;
}