Cod sursa(job #1611111)

Utilizator Athena99Anghel Anca Athena99 Data 23 februarie 2016 22:35:48
Problema Sarpe Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.88 kb
#include <fstream>
#include <string>
#include <vector>

using namespace std;

ifstream fin("sarpe.in");
ofstream fout("sarpe.out");

const int base= 10;

void h_write( vector <int> &x ) {
    for ( int i= (int)x.size()-1; i>=0; --i ) {
        fout<<x[i];
    }
    fout<<"\n";
}

void hh_sub( vector <int> &x, vector <int> &y ) {
    for ( int i= 0; i<(int)x.size(); ++i ) {
        if ( i<(int)y.size() ) {
            x[i]-= y[i];
        }
        if ( x[i]<0 ) {
            x[i]+= base;
            --x[i+1];
        }
    }

    while ( x.back()==0 && (int)x.size()>=2 ) {
        x.pop_back();
    }
}

void hh_mult( vector <int> &x, vector <int> &y ) {
    vector <int> z;
    z.resize( (int)x.size()+(int)y.size() );
    for ( int i= 0; i<(int)x.size(); ++i ) {
        int t= 0;
        for ( int j= 0; j<(int)y.size() || t!=0; ++j ) {
            z[i+j]+= t;
            if ( j<(int)y.size() ) {
                z[i+j]= z[i+j]+x[i]*y[j];
            }
            t= z[i+j]/base;
            z[i+j]%= base;
        }
    }
    while ( z.back()==0 && (int)z.size()>=2 ) {
        z.pop_back();
    }

    x= z;
}

int main(  ) {
    string s;
    fin>>s;
    vector <int> n;
    for ( int i= (int)s.size()-1; i>=0; --i ) {
        n.push_back(s[i]-'0');
    }

    if ( (int)n.size()==1 && n[0]==1 ) {
        fout<<"2\n";
    } else {
        vector <int> sol, aux;
        sol= n;
        hh_mult(sol, n);
        hh_sub(sol, n);

        sol[0]+= 2;
        for ( int i= 0; i<(int)sol.size(); ++i ) {
            if ( sol[i]>base ) {
                if ( i==(int)sol.size()-1 ) {
                    sol.push_back(0);
                }

                ++sol[i+1];
                sol[i]-= base;
            }
        }

        aux.push_back(2);
        hh_mult(sol, aux);

        h_write(sol);
    }

    return 0;
}