Cod sursa(job #2219806)

Utilizator ksanyi2000Kalman Sandor ksanyi2000 Data 9 iulie 2018 19:08:25
Problema Next Scor 70
Compilator cpp Status done
Runda Arhiva de probleme Marime 5.96 kb
#include <iostream>
#include <fstream>
#include <cstring>
using namespace std;

void beolvasas(int tomb[], ifstream &in)
{
    char *szam = new char[1000005];

    in.get(szam,1000005);
    in.get();
    int n = strlen(szam);
    for(int i=0; i<n; i++)
        tomb[i] = szam[n-i-1] - '0';
    tomb[n] = -1;

    delete []szam;
}


void masol(int cel[], int forras[])
{
    int k=0;
    while(forras[k] != -1)
    {
        cel[k] = forras[k];
        k++;
    }
    cel[k] = -1;
}

bool nagyobb_vagy_egyenlo(int tomb1[], int tomb2[])
{
    int i = 0;
    bool felt = true;

    while(tomb1[i] != -1 && tomb2[i] != -1)
    {
        if(tomb1[i] > tomb2[i])
            felt = true;
        else if (tomb1[i] < tomb2[i])
            felt = false;
        i++;
    }

    if(tomb1[i] != -1)
        return true;

    if(tomb2[i] != -1)
        return false;

    return felt;
}


void osszead(int cel[], int forras[])
{
    int maradek = 0;
    int i;
    for(i=0; forras[i]!=-1; i++)
    {
        if(cel[i] == -1)
        {
            cel[i] = 0;
            cel[i+1] = -1;
        }
        int osszeg = cel[i] + forras[i] + maradek;
        cel[i] = osszeg%10;
        maradek = osszeg/10;
    }
    while(maradek)
    {
        if(cel[i] == -1)
        {
            cel[i] = 0;
            cel[i+1] = -1;
        }
        int osszeg = cel[i] + maradek;
        cel[i] = osszeg%10;
        maradek = osszeg/10;
        i++;
    }
}


void kivonas(int cel[], int forras[]) // cel[] >= forras[], cel[] - forras[] = cel[] !!!
{
    int i=0;
    if(cel[i] == -1)
    {
        cel[i] = 0;
        cel[i+1] = -1;
    }
    while(forras[i]!=-1)
    {
        if(cel[i] < forras[i])
        {
            if(cel[i+1] == 0)
            {
                cel[i]+=10;
                int j=i+1;
                while(cel[j]==0)
                {
                    cel[j]+=9;
                    j++;
                }
                cel[j]--;
            }
            else
            {
                cel[i] += 10;
                cel[i+1]--;
            }
        }
        cel[i] -= forras[i];
        i++;
    }

    while(cel[i]!=-1) i++;
    i--;

    while(cel[i]==0)
    {
        cel[i] = -1;
        i--;
    }
}


void megfordit(int tomb[], int n)
{
    int i=0;
    while(i < n-i-1)
    {
        int a = tomb[i];
        tomb[i] = tomb[n-i-1];
        tomb[n-i-1] = a;
        i++;
    }
}


void osztas(int osztando[], int oszto[])
{
    int *hanyados = new int[1000005];
    int i=0, h=0;

    int k=0;
    while(oszto[k] != -1) k++;
    while(k!=0 && oszto[k-1]==0) k--;
    oszto[k] = -1;

    if(osztando[0] == -1)
    {
        oszto[0] = -1;
        delete []hanyados;
        return;
    }
    if(oszto[0] == -1)
    {
        osztando[0] = -1;
        delete []hanyados;
        return;
    }

    while(osztando[i] != -1) i++;
    i--;

    while(i >= 0)
    {
        int db = 0;
        while(nagyobb_vagy_egyenlo(osztando+i, oszto))
        {
            kivonas(osztando+i, oszto);
            db++;
        }
        hanyados[h++] = db;
        i--;
    }

    megfordit(hanyados, h);

    if(h == 0)
        hanyados[0] = -1;
    else
    {
        while(hanyados[h-1] == 0) h--;
        hanyados[h] = -1;
    }

    k=0;
    while(hanyados[k] != -1)
    {
        oszto[k] = hanyados[k];
        k++;
    }
    oszto[k] = -1;

    k=0;
    while(osztando[k] != -1) k++;
    while(k!=0 && osztando[k-1]==0) k--;
    osztando[k] = -1;

    delete []hanyados;
}


void szorzas(int szorzat[], int tomb1[], int tomb2[])
{
    int tizedes = 0;
    int i=0;
    int *tomb3 = new int[1000005];

    if(tomb1[i]==-1 || tomb2[i]==-1)
    {
        szorzat[0] = 0;
        szorzat[1] = -1;
        delete []tomb3;
        return;
    }

    while(tomb1[i] != -1)
    {
        int j=0;
        int maradek = 0;
        tomb3[0] = 0;
        tomb3[1] = -1;

        while(tomb2[j] != -1)
        {
            if(tomb3[j] == -1)
            {
                tomb3[j] = 0;
                tomb3[j+1] = -1;
            }
            int osszeg = tomb3[j] + tomb2[j]*tomb1[i] + maradek;
            tomb3[j] = osszeg%10;
            maradek = osszeg/10;
            j++;
        }

        while(maradek)
        {
            if(tomb3[j] == -1)
            {
                tomb3[j] = 0;
                tomb3[j+1] = -1;
            }
            int osszeg = tomb3[j] + maradek;
            tomb3[j] = osszeg%10;
            maradek = osszeg/10;
            j++;
        }

        j=0;

        while(tomb3[j]!=-1) j++;
        while(j>=0)
        {
            tomb3[j+tizedes] = tomb3[j];
            j--;
        }
        for(int x=0; x<tizedes; x++)
            tomb3[x] = 0;

        osszead(szorzat, tomb3);
        i++;
        tizedes++;
    }

    while(szorzat[i]!=-1) i++;
    i--;
    while(szorzat[i]==0)
    {
        szorzat[i] = -1;
        i--;
    }
    delete []tomb3;
}


void feladat(int tomb1[], int tomb2[])
{
    int *szorzat = new int[1000005];
    int *D = new int[1000005];
    szorzat[0] = -1;

    masol(D, tomb2);

    osztas(tomb1, tomb2);

    if(tomb1[0] != -1)
    {
        int egy[] = {1, -1};
        osszead(tomb2, egy);
    }

    szorzas(szorzat, D, tomb2);

    masol(tomb2, szorzat);
}


void kiir(int tomb[], ofstream &out)
{
    if(tomb[0] == -1)
    {
        out << 0;
        return;
    }
    int i=0;
    while(tomb[i]!=-1) i++;
    i--;
    while(i>=0) out<<tomb[i--];
}
int main()
{
    ifstream in("next.in");
    ofstream out("next.out");

    int *tomb1 = new int[1000005];
    int *tomb2 = new int[1000005];

    beolvasas(tomb1, in);
    beolvasas(tomb2, in);

    feladat(tomb1, tomb2);

    kiir(tomb2, out);

    delete []tomb2;
    delete []tomb1;

    in.close();
    out.close();
}