Cod sursa(job #1778072)

Utilizator VictoriaNevTascau Victoria VictoriaNev Data 13 octombrie 2016 13:32:49
Problema Next Scor 20
Compilator cpp Status done
Runda Arhiva de probleme Marime 6.77 kb
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <iostream>
using namespace std;
const int MAX_DIGITS=10000;
const int BASE=10;
const int MAX_INT=(1LL<<31)-1;
char s[MAX_DIGITS+5];
class HugeN
{
private:
    int x[MAX_DIGITS+5];
public:
    HugeN()
    {
        x[0]=1;
        for(int i=1; i<=MAX_DIGITS; i++)
            x[i]=0;
    }

    HugeN(int nr)
    {
        for(int i=1; i<=MAX_DIGITS; i++)
            x[i]=0;
        do
        {
            x[++x[0]]=nr%10;
            nr/=BASE;
        }
        while(nr);
    }

    HugeN(HugeN &other)
    {
        for(int i=0; i<=MAX_DIGITS; i++)
            x[i]=0;
        memcpy(x, other.x, sizeof(other.x));
    }

    HugeN(char *s)
    {
        x[0]=strlen(s);
        for(int i=1; i<=x[0]; i++)
            x[i]=s[x[0]-i]-'0';
    }

    void read()
    {
        x[0]=0;
        char c;
        while (scanf("%c",&c)!=EOF && c!='\n')
        {
            c=c-'0';
            x[(int)++x[0]]=c;
        }
        for (int i=1; i<=(x[0]>>1); i++)
        {
            char aux;
            aux=x[i];
            x[i]=x[x[0]-i+1];
            x[x[0]-i+1]=aux;
        }
    }

    void print()
    {
        for (int i=x[0]; i>=1; i--)
        {
            printf("%d",(int)x[i]);
        }
    }

    int cmp(const HugeN &other);
    HugeN operator + (const HugeN &other);
    HugeN operator += (const HugeN &other);
    HugeN operator - (const HugeN &other);
    HugeN operator - (int k);
    HugeN operator -= (const HugeN &other);
    HugeN operator * (const HugeN &other);
    HugeN operator *= (const HugeN &other);
    HugeN operator * (int k);
    HugeN operator *= (int k);
    HugeN operator / (int k);
    HugeN operator / (const HugeN &other);
    HugeN operator /= (int k);
    HugeN operator ^ (int k);
    long long operator % (long long k);
    HugeN operator % (const HugeN &other);
    bool operator > (const HugeN &other);
    bool operator >= (const HugeN &other);
    bool operator < (const HugeN &other);
    bool operator <= (const HugeN &other);
    bool operator == (const HugeN &other);
    bool operator != (const HugeN &other);

};

int HugeN::cmp(const HugeN &other)
{
    int i;
    if(x[0]>other.x[0])
        return 1;
    if(x[0]<other.x[0])
        return -1;
    for(int i=x[0]; i>=1; i--)
        if(x[i]>other.x[i])
            return 1;
        else if(x[i]<other.x[i])
            return -1;
    return 0;
}

HugeN HugeN::operator + (const HugeN &other)
{
    ///temp.x=x+other.x
    HugeN temp;
    temp.x[0]=x[0]>other.x[0] ? x[0] : other.x[0];
    int tr=0, aux;
    for(int i=1; i<=temp.x[0]; i++)
    {
        aux=x[i]+other.x[i]+tr;
        temp.x[i]=aux%BASE;
        tr=aux/BASE;
    }
    if(tr)
        temp.x[++temp.x[0]]=tr;
    return temp;
}

HugeN HugeN::operator += (const HugeN &other)
{
    ///x=x+other.x
    x[0]=x[0]>other.x[0] ? x[0] : other.x[0];
    int tr=0, aux, i;
    for(int i=1; i<=x[0]; i++)
    {
        aux=x[i]+other.x[i]+tr;
        x[i]=aux%BASE;
        tr=aux/BASE;
    }
    if(tr)
        x[++x[0]]=tr;
    return *this;
}

HugeN HugeN::operator - (const HugeN &other)
{
    ///temp.x=x-other.x;
    HugeN temp;
    temp.x[0]=x[0]>other.x[0] ? x[0] : other.x[0];
    int aux, tr=0;
    for(int i=1; i<=temp.x[0]; i++)
    {
        if(x[i]-tr>=other.x[i])
        {
            temp.x[i]=x[i]-other.x[i]-tr;
            tr=0;
        }
        else
        {
            temp.x[i]=(x[i]-tr+BASE-other.x[i])%BASE;
            tr=1;
        }
    }
    while(!temp.x[temp.x[0]] && temp.x[0]>1)
        temp.x[0]--;
    return temp;
}

HugeN HugeN::operator -= (const HugeN &other)
{
    ///x=x-other.x
    x[0]=x[0]>other.x[0] ? x[0] : other.x[0];
    int tr=0, aux, i;
    for(int i=1; i<=x[0]; i++)
    {
        if(x[i]-tr>other.x[i])
        {
            x[i]=x[i]-other.x[i]-tr;
            tr=0;
        }
        else
        {
            x[i]=(x[i]-tr+BASE-other.x[i])%BASE;
            tr=1;
        }
    }

    while(!x[x[0]] && x[0]>1)
        x[0]--;
    return *this;
}

HugeN HugeN::operator - (int k)
{
    ///x=x-int
    int tr=0, aux, i;
    for(int i=1; i<=x[0]; i++, k/=BASE)
    {
        if(x[i]-tr>k%10)
        {
            x[i]=x[i]-k%BASE-tr;
            tr=0;
        }
        else
        {
            x[i]=(x[i]-tr+BASE-k%BASE)%BASE;
            tr=1;
        }
    }

    while(!x[x[0]] && x[0]>1)
        x[0]--;
    return *this;
}

HugeN HugeN::operator * (const HugeN &other)
{
    ///temp.x=x*other.x
    HugeN temp;
    int tr=0, tr2=0, sth, aux, len=0, ad=1, ok=0;
    for(int j=1; j<=other.x[0]; j++)
    {

        len=ad;
        for(int i=1; i<=x[0]; i++)
        {
            aux=x[i]*other.x[j]+tr;
            tr=aux/BASE;
            sth=temp.x[len]+aux%BASE+tr2;
            tr2=sth/BASE;
            temp.x[len]=sth%BASE;
            len++;
        }
        if(tr)
        {
            temp.x[len]=tr;
            ok=1;
        }
        tr=0;
        ad++;
    }
    if(tr2)
    {
        temp.x[len]+=tr2;
        ok=1;
    }
    if(!ok)
        len--;
    temp.x[0]=len;
    return temp;
}

HugeN HugeN::operator * (int k)
{
    ///temp.x=x*int
    HugeN temp;
    int tr=0, tr2=0, sth, aux, len=0, ad=1, ok=0;
    while(k)
    {

        len=ad;
        for(int i=1; i<=x[0]; i++)
        {
            aux=x[i]*(k%BASE)+tr;
            tr=aux/BASE;
            sth=temp.x[len]+aux%BASE+tr2;
            tr2=sth/BASE;
            temp.x[len]=sth%BASE;
            len++;
        }
        if(tr)
        {
            temp.x[len]=tr;
            ok=1;
        }
        tr=0;
        ad++;
        k/=BASE;
    }
    if(tr2)
    {
        temp.x[len]+=tr2;
        ok=1;
    }
    if(!ok)
        len--;
    temp.x[0]=len;
    return temp;
}

long long HugeN::operator % (long long k)
{
    long long r=0;
    for (int i=x[0]; i>=1; i--)
    {
        r=(r*10+x[i])%k;
    }
    return r;
}

bool HugeN::operator > (const HugeN &other)
{
    if((*this).cmp(other)==1)
        return 1;
    return 0;
}

bool HugeN::operator >= (const HugeN &other)
{
    if((*this).cmp(other)==1 || (*this).cmp(other)==0)
        return 1;
    return 0;
}

bool HugeN::operator < (const HugeN &other)
{
    if((*this).cmp(other)==-1)
        return 1;
    return 0;
}

bool HugeN::operator <= (const HugeN &other)
{
    if((*this).cmp(other)==-1 || (*this).cmp(other)==0)
        return 1;
    return 0;
}

bool HugeN::operator == (const HugeN &other)
{
    if((*this).cmp(other)==0)
        return 1;
    return 0;
}

bool HugeN::operator != (const HugeN &other)
{
    if((*this).cmp(other)==-1 || (*this).cmp(other)==-1)
        return 1;
    return 0;
}

int main()
{
    freopen("next.in","r",stdin);
    freopen("next.out","w",stdout);
    long long k,r;
    HugeN n;
    n.read();
    scanf("%lld", &k);
    r=n%k;
    if(r==0)
        r=k;
    r=k-r;
    HugeN x(r);
    n+=x;
    n.print();
    return 0;
}