Cod sursa(job #3122797)

Utilizator andrei_C1Andrei Chertes andrei_C1 Data 20 aprilie 2023 18:20:06
Problema A+B Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 4.74 kb
#include <bits/stdc++.h>

using namespace std;

ifstream fin("adunare.in");
ofstream fout("adunare.out");

struct Node {
    int val;
    Node *next;
    Node(int val = 0) : val(val), next(nullptr) {}
};

struct bignum {
    int n;
    Node *root;
    bignum(int n = 0) : n(n) {
        root = new Node();
    }
};

const int NMAX = 1e4;

void Read(bignum &a) {
    char s[NMAX + 1];
    fin >> s;
    int n = strlen(s);
    a = bignum(n);
    bignum b = a;
    for(int i = n - 1; i >= 0; i--) {
        b.root->val = s[i] - '0';
        b.root->next = new Node();
        b.root = b.root->next;
    }
}

istream& operator >> (istream &is, bignum &a) {
    Read(a);
    return is;
}

void Write(Node *root) {
    if(root->next != nullptr) {
        Write(root->next);
        fout << root->val;
    }
}

void Write(bignum a) {
    Write(a.root);
}

ostream& operator << (ostream &os, bignum a) {
    Write(a);
    return os;
}

bignum operator + (bignum a, bignum b) {
    bignum d(max(a.n, b.n));
    bignum c = d;

    int t = 0;
    for(int i = 0; i < c.n; i++) {
        int A = 0;
        int B = 0;

        if(a.root->next != nullptr) {
            A = a.root->val;
            a.root = a.root->next;
        }
        if(b.root->next != nullptr) {
            B = b.root->val;
            b.root = b.root->next;
        }

        t += A + B;
        c.root->val = t % 10;
        t /= 10;
        c.root->next = new Node();
        c.root = c.root->next;
    }
    while(t) {
        c.n++;
        c.root->val = t % 10;
        t /= 10;
        c.root->next = new Node();
        c.root = c.root->next;
    }

    return d;
}

int Compare(bignum a, bignum b) {
    if(a.n > b.n) {
        return 1;
    } else if(a.n < b.n) {
        return -1;
    } else {
        int pos = -1, A, B;
        for(int i = 0; i < a.n; i++) {
            if(a.root->val != b.root->val) {
                pos = i;
                A = a.root->val;
                B = b.root->val;
            }
        }

        if(pos == -1) {
            return 0;
        } else {
            if(A > B) {
                return 1;
            } else {
                return -1;
            }
        }
    }
}

bignum operator - (bignum a, bignum b) {
    if(Compare(a, b) == -1) {
        swap(a, b);
    }

    bignum d(max(a.n, b.n));
    bignum c = d;

    int t = 0;
    for(int i = 0; i < c.n; i++) {
        int A = 0;
        int B = 0;

        if(a.root->next != nullptr) {
            A = a.root->val;
            a.root = a.root->next;
        }
        if(b.root->next != nullptr) {
            B = b.root->val;
            b.root = b.root->next;
        }

        t += A - B;
        c.root->val = t % 10;
        t /= 10;
        if(c.root->val < 0) {
            c.root->val += 10;
            t--;
        }
        c.root->next = new Node();
        c.root = c.root->next;
    }

    int pos = -1;
    bignum e = d;
    c.root = d.root;
    for(int i = 0; i < e.n; i++) {
        if(d.root->val != 0) {
            c.root = d.root->next;
            pos = i;
        }
        d.root = d.root->next;
    }
    if(pos == -1) {
        c.root = c.root->next;
        pos = 1;
    }
    e.n = pos;
    c.root->next = nullptr;
    delete c.root->next;
    return e;
}

bignum operator * (bignum a, bignum b) {
    bignum d(a.n + b.n);
    bignum c = d;
    for(int i = 0; i < d.n; i++) {
        c.root->val = 0;
        c.root->next = new Node();
        c.root = c.root->next;
    }

    bignum x = a;
    bignum y = b;
    for(int i = 0; i < a.n; i++) {
        c = d;
        for(int k = 0; k < i; k++)
            c.root = c.root->next;

        y = b;
        for(int j = 0; j < b.n; j++) {
            c.root->val += x.root->val * y.root->val;
            c.root = c.root->next;
            y.root = y.root->next;
        }
        x.root = x.root->next;
    }

    c = d;
    int t = 0;
    for(int i = 0; i < c.n; i++) {
        t += c.root->val;
        c.root->val = t % 10;
        c.root = c.root->next;
        t /= 10;
    }

    while(t) {
        c.root->next = new Node();
        c.root->val = t % 10;
        t /= 10;
    }

    int pos = -1;
    bignum e = d;
    c.root = d.root;
    for(int i = 0; i < e.n; i++) {
        if(d.root->val != 0) {
            c.root = d.root->next;
            pos = i;
        }
        d.root = d.root->next;
    }
    if(pos == -1) {
        c.root = c.root->next;
        pos = 1;
    }
    e.n = pos;
    c.root->next = nullptr;
    delete c.root->next;
    return e;
}

int main() {
    bignum a, b;
    fin >> a >> b;
    fout << a + b << '\n';
    return 0;
}