Pagini recente » Monitorul de evaluare | Cod sursa (job #1449066) | Cod sursa (job #1034863) | Cod sursa (job #975438) | Cod sursa (job #1777075)
#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);
}