Cod sursa(job #1784068)

Utilizator roxana.aeleneiAelenei Roxana roxana.aelenei Data 19 octombrie 2016 19:20:48
Problema Next Scor 60
Compilator cpp Status done
Runda Arhiva de probleme Marime 9.46 kb
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
const int MAX_DIGITS=100001;
const int BASE=10;
//const int MAX_INT=(1LL << 31)-1;
char s[MAX_DIGITS+5];
using namespace std;

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=0; i <= MAX_DIGITS; i++)
            x[i]=0;
        do
        {
            x[++x[0]] = nr%10;
        }
        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 print()
    {
        int i;
        for(i=x[0]; i >= 1; i--)
            printf("%d", x[i]);
        printf("\n");
    }

    bool null();
    int nr_digits();
    void atr_int(int nr);
    void rev ();
    void reset ();
    void cpy_char(char *s);
    int cmp(const HugeN &other);

    //Operatori logici
    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);

    //Operatori aritmetici
    HugeN operator +(const HugeN &other);
    HugeN operator -(const HugeN &other);
    HugeN operator -(int k);
    HugeN operator *(int k);
    HugeN operator *(const HugeN &other);
    HugeN operator /(int k);
    HugeN operator /(const HugeN &other);
    long long operator % (long long k);
    HugeN operator % (const HugeN &other);
    HugeN operator ^ (int k);
    HugeN operator +=(const HugeN &other);
    HugeN operator -=(const HugeN &other);
    HugeN operator *=(int k);
    HugeN operator *=(const HugeN &other);
    HugeN operator /=(int k);
    HugeN operator +=(long long k);
};

bool HugeN :: null()
{

    if(x[0]==1 && x[1]==0)
        return 1;
    return 0;
}

int HugeN :: nr_digits()
{

    return x[0];
}

void HugeN :: atr_int(int nr)
{
    memset(x,0,sizeof(0));
    do
    {
        x[++x[0]]= nr%10;
        nr/=BASE;
    }
    while(nr);
}

void HugeN :: rev()
{
    for(int i=1; i<=x[0]/2; i++)
        swap(x[i],x[x[0]-i+1]);
    while(x[x[0]] == 0 && x[0] > 1)
        x[0]--;
}

void HugeN :: reset()
{
    for(int i=1; i <=MAX_DIGITS; i++)
        x[i]=0;
    x[0]=1;
}

void HugeN :: cpy_char(char *s)
{

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

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(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;
}

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

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

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

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

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

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

//Operatori aritmetici

HugeN HugeN :: operator+(const HugeN &other)
{
    int i,tr=0,aux;
    HugeN temp;
    temp.x[0]=x[0] > other.x[0] ? x[0] : other.x[0];
    for(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 - (int k)
{
    HugeN temp;
    int aux, impr=0;
    temp.x[0]=x[0];
    for(int i=1; i <= temp.x[0]; i++)
    {
        aux=x[i]-k%10-impr;
        impr=0;
        if(aux < 0)
        {
            aux+=10;
            impr = 1;
        }
        temp.x[i] = aux %BASE;
        k /=10;
    }
    while (temp.x[temp.x[0]] == 0 && temp.x[0] > 1)
        temp.x[0]--;

    return temp;
}

HugeN HugeN :: operator+=(const HugeN &other)
{
    x[0]=x[0] > other.x[0] ? x[0] : other.x[0];
    int tr=0, aux, i;
    for(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+=(long long k)
{
    HugeN temp;
    temp.x[0]=x[0];
    long long aux,i;
    for(i=1; i<=temp.x[0]; i++)
    {
        aux=x[i]+k;
        x[i]=aux%BASE;
        k=aux/BASE;
    }
    if(k)
        x[++x[0]]=k;
    return *this;
}

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

    return temp;
}

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

}

HugeN HugeN :: operator *(int k)
{
    HugeN temp;
    temp.x[0]=x[0];
    int tr=0,aux,i;
    for(i=1; i<=temp.x[0]; i++)
    {
        aux=x[i]*k+tr;
        temp.x[i]=aux %BASE;
        tr=aux/BASE;
    }
    while(tr)
    {
        temp.x[++temp.x[0]]=tr%BASE;
        tr/=BASE;
    }
    return temp;
}

HugeN HugeN :: operator *(const HugeN &other)
{
    HugeN temp;
    if(x[x[0]] == 0 || other.x[other.x[0]]==0)
        return temp;
    temp.x[0]=x[0]+other.x[0]-1;
    int tr=0, i,j,aux;
    for(i=1; i <=x[0]; i++)
        for(j=1; j <= other.x[0]; j++)
        temp.x[i+j-1]+=x[i]*other.x[i];

    for(i=1; i<=temp.x[0]; i++)
        {
            aux=temp.x[i]+tr;
            temp.x[i]=aux%BASE;
            tr=aux/BASE;
        }
        while(tr)
        {
            temp.x[++temp.x[0]]=tr % BASE;
            tr/=BASE;
        }
        return temp;
}

HugeN HugeN :: operator / (int k)
{
    HugeN temp;
    temp.x[0]=x[0];
    int i,r=0,aux;
    for(i=temp.x[0]; i>= 1; i--)
    {
        aux=r*10+x[i];
        temp.x[i]=aux/k;
        r=aux%k;
    }
    while (temp.x[temp.x[0]] == 0)
        temp.x[0]--;
    return temp;
}

HugeN HugeN :: operator / (const HugeN &other)
{
    HugeN c;
    HugeN r;
    int i;
    c.x[0]=x[0];
    for(i=x[0]; i>= 1; i--)
    {
        r=r*10;
        r.x[1]=x[i];
        c.x[i]=0;
        while(r >= other)
        {
            c.x[i]=c.x[i]+1;
            r=r-other;
        }
    }
    while(c.x[c.x[0]] == 0 && c.x[0] > 1)
        c.x[0]--;
    return c;
}

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

}

HugeN HugeN :: operator % (const HugeN &other)
{
    HugeN c;
    HugeN r;
    int i;
    for(i=x[0]; i>=1; i--)
    {
        r=r*10;
        r.x[1]=x[i];
        while(r>=other)
            r=r-other;
    }

    return r;
}

HugeN HugeN :: operator ^ (int k)
{
    HugeN ans(1);
    HugeN aux(*this);
    for(; k; k>>=1)
    {
        if (k& 1)
             ans*=aux;
        aux *=aux;
    }
    return ans;
}

HugeN HugeN :: operator *=(int k)
{
    int tr=0, aux,i;
    for(i=1; i <=x[0]; i++)
    {
        aux=x[i]*k+tr;
        x[i]=aux%BASE;
        tr=aux/BASE;
    }
    while(tr)
    {
        x[++x[0]]=tr%BASE;
        tr/=BASE;
    }
    return *this;
}

HugeN HugeN :: operator *=(const HugeN &other)
{
    HugeN temp;
    if(x[x[0]] == 0 || other.x[other.x[0]] == 0)
    {
        x[0] = 1;
        x[1] = 0;
        return *this;
    }
    temp.x[0]=x[0]+other.x[0]-1;
    int tr=0,i,j,aux;
    for(i=1; i <= x[0]; i++)
        for(j=1; j<=other.x[0]; j++)
            temp.x[i+j-1]+=x[i]*other.x[i];

    for(i=1; i <= temp.x[0]; i++)
    {
        aux=temp.x[i]+tr;
        temp.x[i]=aux % BASE;
        tr=aux/BASE;
    }

    while(tr)
    {
        temp.x[++temp.x[0]]=tr%BASE;
        tr/=BASE;
    }
    (*this)=temp;
    return *this;
}

HugeN HugeN :: operator /= (int k)
{
    int i,r=0,aux;
    for(i=x[0]; i>=1; i--)
    {
        aux=r*10+x[i];
        x[i]=aux/k;
        r=aux%k;
    }
    while(x[x[0]]==0)
        x[0]--;
    return *this;
}
int main()
{
    freopen("next.in", "r", stdin);
    freopen("next.out", "w", stdout);
    long long d,rest,a;
    gets(s);
    HugeN n(s);
    scanf("%lld", &d);
    rest=n%d;
    if(rest)
        a=d-rest;

        n+=a;
        n.print();

    return 0;
}