Cod sursa(job #1777075)

Utilizator radu.millio15Radu Millio radu.millio15 Data 12 octombrie 2016 00:55:05
Problema Next Scor 20
Compilator cpp Status done
Runda Arhiva de probleme Marime 8.58 kb
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <cmath>
#include <stdio.h>
using namespace std;
const int MAX_DIGITS = 10000;
const int BASE = 10;
const int MAX_INT = (1LL << 31) -1;  /// 1 << 31 echivalent cu 2^31; cel mai mare int este 2^31 -1
char s[MAX_DIGITS+5];                   ///LL -> pt a putea fi stocat in tip long long
class HugeN
{
    private: int x[MAX_DIGITS+5];
    public:
        HugeN()
        {
            x[0] = 1;
            /*for(int i = 1; i <= MAX_DIGITS; i ++)
                x[i] = 0*/
            memset(x, 0, sizeof(x));
        }
        HugeN(int nr)
        {
            for(int i = 0; i <= MAX_DIGITS; i ++)
                x[i] = 0;
            do{
                x[++x[0]] = nr%BASE;
                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';
        }
        int marime()
        {
            return x[0];    ///afisam numarul de cifre
        }
        int elem(int n)     ///afisam a "n" -a cifra
        {
            return x[n];
        }
        void print()        ///printam in consola
        {
            int i;
            for(i = x[0]; i >= 1; i --)
                printf("%d", x[i]);
            printf("\n");
        }
        void afisare(FILE *fout)        ///printam in fisierul primit ca parametru
        {
            int i;
            for(i=x[0]; i>=1; i--)
                fprintf(fout, "%d", x[i]);
            fprintf(fout, "\n");
        }
        int cmp(const HugeN &other);
        HugeN operator + (const HugeN &other);     ///facut
        HugeN operator - (const HugeN &other);      ///facut
        HugeN operator - (int k);
        HugeN& operator * (int k);                  ///facut
        HugeN& operator * (const HugeN &other);     ///facut
        HugeN operator / (int k);
        HugeN operator / (const HugeN &other);      ///???
        long long operator % (long long k);               ///facut
        HugeN operator % (const HugeN &other);
        HugeN operator ^ (int k);
        HugeN operator += (const HugeN &other);     ///facut
        HugeN operator -= (const HugeN &other);
        HugeN operator *= (const HugeN &other);
        HugeN operator *= (int k);
        HugeN operator /= (int k);
        bool operator > (const HugeN &other);       ///facut
        bool operator >= (const HugeN &other);      ///facut
        bool operator < (const HugeN &other);       ///facut
        bool operator <= (const HugeN &other);      ///facut
        bool operator == (const HugeN &other);      ///facut
        bool operator != (const HugeN &other);      ///facut
};
long long HugeN::operator % (long long k)
{
    long long r=0;
    for(int i=x[0]; i>=1; i--)
    {
        r=r*10+x[i];
        r=r%k;
    }
    return r;
}
HugeN HugeN::operator + (const HugeN &other)
{
    HugeN temp; ///temp.x = x + other.x
    temp.x[0] = x[0] > other.x[0] ? x[0] : other.x[0];
    int tr=0,aux, i;
    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 += (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(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)
{
    HugeN temp;
    HugeN schimb;
    temp.x[0] = x[0] > other.x[0] ? x[0] : other.x[0];
    int semn=+1, i, aux, k;
    if (cmp(other)==-1)         ///daca rezultatul ne va da cu minus, ideea este sa interschimbam vectorii astfel in cat sa
    {                           ///obtinem o diferenta pozitiva, apoi ii voi schimba semnul in "-"
        semn=-1;
        for(i=0; i<=temp.x[0]; i++)
            schimb.x[i]=other.x[i];     ///folosesc un vector auxiliar, "schimb" care este copia vectorului primit ca parametru :"other"
    }                                   ///pentru ca "other" este declarat const si, deci, nu poate fi modificat (interschimbat direct cu primul vector)
    if (semn==-1)       ///facem acelasi lucru ca la semn=+1, doar ca schimbam semnul primei cifre
    {
        for(i=1; i<=temp.x[0]; i++)
        {
            aux=schimb.x[i]-x[i];
            if(aux<0)
            {
                aux=aux+10;
                k=i+1;
                while(schimb.x[k]==0)
                {
                    schimb.x[k]=9;
                    k++;
                }
                schimb.x[k]--;

            }
            temp.x[i]=aux;
        }
        while(temp.x[i-1]==0)   ///folosesc "i-1" pentru ca for-ul are ca pas i++
        {                          ///deci se va termina cu o casuta mai tarziu
            i--;
            temp.x[0]--;
        }
        temp.x[i-1]=-temp.x[i-1];       ///schimbam semnul primei cifre
    }
    else{
        for(i=1; i<=temp.x[0]; i++)
        {
            aux=x[i]-other.x[i];
            if(aux<0 )
            {
                aux=aux+10;
                k=i+1;
                while(x[k]==0)
                {
                    x[k]=9;
                    k++;
                }
                x[k]--;
            }
            temp.x[i]=aux;
        }
        while(temp.x[i-1]==0)       ///folosesc "i-1" deoarece for-ul are ca pas i++
        {                           ///deci se va termina cu o casuta mai tarziu
            i--;
            temp.x[0]--;
        }
    }
    return temp;
}

HugeN& HugeN::operator * (int k)
{
    ///temp = x * k x=obiectul curent pentru care lucreza functia
    HugeN temp;
    int t=0,i,aux;
    temp.x[0]=x[0];
    for(i=1; i<=x[0]; i++)
        temp.x[i]=x[i]*k;
    for(i=1; i<=temp.x[0]; i++)
    {
        aux=temp.x[i]+t;
        temp.x[i]=aux%BASE;
        t=aux/BASE;
    }
    int l=temp.x[0];
    while(t)
    {
        temp.x[0]++; ++l;
        temp.x[l]=t%BASE;
        t=t/BASE;
    }
    return temp;
}

HugeN& HugeN::operator * (const HugeN &other)
{
    ///temp= x* other;
    HugeN temp;
    int t=0, i, j, aux;
    temp.x[0]=x[0]+other.x[0]-1;
    for(j=1; j<=other.x[0]; j++)
        for(i=1; i<=x[0]; ++i)
            temp.x[i+j-1]+=x[i]*other.x[j];
    for(i=1; i<=temp.x[0]; i++)
    {
        aux=temp.x[i]+t;
        temp.x[i]=aux%BASE;
        t=aux/BASE;
    }
    int l=temp.x[0];
    while(t)
    {
        temp.x[0]++; ++l;
        temp.x[l]=t%BASE;
        t=t/BASE;
    }
    return temp;
}

HugeN HugeN::operator / (int k)
{
    HugeN temp;
    int cnt=0;
    while(k)
    {
        cnt++;
        k=k/10;
    }
    temp.x[0]=x[0]-cnt+1;
    int aux=0, i;
    for(i=x[0]; i>=1; i--)
    {
        aux=aux*10+x[i];
        if(aux<k)
            temp.x[temp.x[0]--]=0;
        else{
            temp.x[temp.x[0]--]=aux/k;
            aux=aux%k;
        }
    }
    return temp;
}
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;
}

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

int main()
{
    FILE *fin, *fout;
    fin=fopen("next.in", "r");
    fout=fopen("next.out", "w");
    long long d,r;
    char line[1000005];
    fscanf(fin, "%s", &line);
    HugeN a(line);
    fscanf(fin, "%lld", &d);
    r=a%d;
    a+=d-r;
    a.afisare(fout);


}