Cod sursa(job #2673159)

Utilizator NeacsuMihaiNeacsu Mihai NeacsuMihai Data 16 noiembrie 2020 02:25:44
Problema Next Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.5 kb
#include <iostream>
#include <fstream>
#include <cstring>

using namespace std;

ifstream fin ("next.in");
ofstream fout ("next.out");
char s[2000001];
typedef int Huge[2000001];
Huge n, d, z, r;
void adunare(Huge a, Huge b, Huge c)
{
    //c<- a+b
    int i, r=0;
    for(i=a[0]+1; i<=b[0]; i++) a[i]=0;
    for(i=b[0]+1; i<=a[0]; i++) b[i]=0;
    c[0]=max(a[0], b[0]);
    for(i=1; i<=c[0]; i++)
    {
        c[i]=a[i]+b[i]+r;
        r=c[i]/10;
        c[i]%=10;
    }
    if(r)
    {
        c[++c[0]]=r;
    }
}
void scadere(Huge a, Huge b)
{
    //a=a-b, se garanteaza a>=b
    int i, r=0;
    for(i=b[0]+1; i<=a[0]; i++) b[i]=0;
    for(i=1; i<=a[0]; i++)
    {
        a[i]=a[i]-r-b[i];
        r=0;
        if(a[i]<0)
        {
            r=1;
            a[i]+=10;
        }
    }
    while(a[a[0]]==0) a[0]--;
}
int comparare(Huge a, Huge b)
{
    if(a[0]<b[0]) return -1;
    if(a[0]>b[0]) return 1;
    for(int i=a[0]; i>0; i--)
    {
        if(a[i]>b[i]) return 1;
        else if(b[i]>a[i]) return -1;
    }
    return 0;
}
void inmultire10(Huge a)
{
    for(int i=a[0]+1; i>=2; i--)
    {
        a[i]=a[i-1];
    }
    a[0]++;
}
void impartire(Huge a, Huge b, Huge c)
{
    //c=a/b;
    int i; r[0]=1; r[1]=0;
    for(i=a[0]; i>0; i--)
    {
        inmultire10(r);
        r[1]=a[i];
        c[i]=0;
        while( comparare(b, r)!=1 )
        {
            c[i]++;
            scadere(r, b);
        }

        /*a[i]=r*10+a[i];
        r=a[i]%x;
        a[i]/=x;*/
    }
    while(c[c[0]]==0 && c[0]>1) c[0]--;
}
void inmultire(Huge a, Huge b, Huge c)
{
    int i, j, r=0;
    c[0]=a[0]+b[0]-1;
    for(i=1; i<=a[0]; i++)
    {
        for(j=1; j<=b[0]; j++)
        {
            c[i+j-1]=a[i]*b[j];
        }
    }
    for(i=1; i<=c[0]; i++)
    {
        c[i]=c[i]+r;
        r=c[i]/10;
        c[i]=c[i]%10;
    }
    //while(c[c[0]]==0) c[0]--;
}
void afisare(Huge a)
{
    for(int i=a[0]; i>0; i--) fout<<a[i];
    fout<<"\n";
}
void citire()
{
    int i, str;
    fin.getline(s, 1000001);
    str=strlen(s);
    n[0]=str;
    for(i=str-1; i>=0; i--)
    {
        n[str-i]=s[i]-'0';
    }
    fin.getline(s, 1000001);
    str=strlen(s);
    d[0]=str;
    for(i=str-1; i>=0; i--)
    {
        d[str-i]=s[i]-'0';
    }
}
Huge unu;
int main()
{
    citire();

    unu[0]=1; unu[1]=1;
    adunare(n, d, z);
    scadere(z, unu);
    impartire(z, d, n);
    inmultire(d, n, z);
    afisare(z);
}