Spoj GEOPROB – Cpp solution

The idea is first express A as a function of B, C and D. It’s quite easy to see that the answer would be:
A = 2*C – B – D.
Since the numbers can be quite big, you will have to write your own methods for addition and subtraction of big numbers (200 digits).

#include <cstdio>
#include <cstring>
#include <vector>
#include <algorithm>
#include <iostream>
using namespace std;

vector<int>  b(201),c(201),d(201);

void print(const vector<int> & V) {
    for (int i = 0; i < V.size(); ++i) {
        printf("%d", V[i]);
    }
    printf("n");
}

void clean(vector<int> & V) {
    while(V[0] == 0) V.erase(V.begin());
}

vector<int> operator +(const vector<int> & A, const vector<int> & B) {
    vector<int> Arev = A, Brev = B;
    reverse(Arev.begin(), Arev.end());
    reverse(Brev.begin(), Brev.end());
    vector<int> res;
    int sz = (max(Arev.size(), Brev.size()));
    res.resize(sz+1);

    for (int i = 0; i < sz; ++i) {
        int f1=0,f2=0,f3 = 0;
        if (Arev.size() > i) {
            f1 = Arev[i];
        }
        if (Brev.size() > i) {
            f2 = Brev[i];
        }
        f3 = res[i];
        int f4 = f1+f2+f3;
        int dig = f4%10;
        int se = (f4/10)%10;
        res[i] = dig;
        res[i+1] = se;
    }
    reverse(res.begin(), res.end());
    return res;

}

vector<int> operator -(const vector<int> & A, const vector<int> & B) {
    vector<int> Arev = A, Brev = B;
    reverse(Arev.begin(), Arev.end());
    reverse(Brev.begin(), Brev.end());
    vector<int> res;
    int sz = (max(Arev.size(), Brev.size()));
    res.resize(sz);
    for (int i = 0; i < sz; ++i) {
        int f1 = 0, f2 = 0;
        if (Arev.size() > i) {
            f1 = Arev[i];
        }
        if (Brev.size() > i) {
            f2 = Brev[i];
        }
        f2 += res[i];
        res[i] = 0;
        int f3 = (f1-f2);
        if (f3 < 0) {
            f3 += 10;
            res[i] = f3%10;
            res[i+1] = 1;
        } else {
            res[i] = f3;
        }
    }
    reverse(res.begin(), res.end());
    return res;
}

void readS(vector<int> * buf) {
    buf->clear();
    buf->reserve(201);
    string s;
    cin >> s;
    for (int i = 0; i < s.length(); ++i) {
        buf->push_back(s[i]-'0');
    }
}

void read() {
    readS(&b);
    readS(&c);
    readS(&d);
}

void answer() {
    vector<int> dc = c+c;
    clean(dc);
    dc = dc - b;
    clean(dc);
    dc = dc - d;
    clean(dc);
    print(dc);
}

int main() {
    int t;
    cin >> t;
    while (t--) {
        read();
        answer();
    }
    return 0;
}

Leave a Reply

Your email address will not be published. Required fields are marked *