exercises/cs101/2025mid/exam_2025mid_09_bigfloat.cpp

#include <algorithm>
#include <array>
#include <iostream>
#include <vector>

constexpr int char_to_digit(char c) {
    if (c >= '0' && c <= '9') { return static_cast<short>(c - '0'); }
    if (c >= 'A' && c <= 'Z') { return static_cast<short>(c - 'A' + 10); }
    throw std::invalid_argument("Invalid char as digit");
}

constexpr char digit_to_char(int digit) {
    if (digit >= 0 && digit <= 9) { return static_cast<char>('0' + digit); }
    return static_cast<char>('A' + digit - 10);
}

class BigFloat {
public:
    std::array<std::vector<int>, 2> digit_vectors;
    bool negative = false;
    unsigned short base = 10;

    explicit BigFloat(std::string s, unsigned short base = 10) : base(base) {
        int i = 0;
        if (s[0] == '-') { negative = true, i++; }
        for (; i < s.size() && s[i] != '.'; i++) { digit_vectors[0].push_back(char_to_digit(s[i])); }
        std::reverse(digit_vectors[0].begin(), digit_vectors[0].end());
        i++;
        for (; i < s.size(); i++) { digit_vectors[1].push_back(char_to_digit(s[i])); }
    }

    void normalize() {
        digit_vectors[0].push_back(0);
        digit_vectors[1].push_back(0);
        for (int i = static_cast<int>(digit_vectors[1].size() - 2); i >= 0; i--) {
            if (digit_vectors[1][i + 1] >= base) {
                digit_vectors[1][i] += digit_vectors[1][i + 1] / base;
                digit_vectors[1][i + 1] %= base;
            }
            if (digit_vectors[1][i + 1] < 0) {
                int borrowed = -(digit_vectors[1][i + 1] + 1) / base + 1;
                digit_vectors[1][i] -= borrowed;
                digit_vectors[1][i + 1] += base * borrowed;
            }
        }
        if (digit_vectors[1][0] >= base) {
            digit_vectors[0][0] += digit_vectors[1][0] / base;
            digit_vectors[1][0] %= base;
        }
        if (digit_vectors[1][0] < 0) {
            int borrowed = -(digit_vectors[1][0] + 1) / base + 1;
            digit_vectors[0][0] -= borrowed;
            digit_vectors[1][0] += base * borrowed;
        }
        for (int i = 1; i < digit_vectors[0].size(); i++) {
            if (digit_vectors[0][i - 1] >= base) {
                digit_vectors[0][i] += digit_vectors[0][i - 1] / base;
                digit_vectors[0][i - 1] %= base;
            }
            if (digit_vectors[0][i - 1] < 0) {
                int borrowed = -(digit_vectors[0][i - 1] + 1) / base + 1;
                digit_vectors[0][i] -= borrowed;
                digit_vectors[0][i - 1] += base * borrowed;
            }
        }

        if (digit_vectors[0][digit_vectors[0].size() - 1] < 0) {
            // digit_vectors[0][digit_vectors[0].size() - 1] = -digit_vectors[0][digit_vectors[0].size() - 1];
            negative = !negative;
            for (auto& digits : digit_vectors) {
                for (auto& digit : digits) { digit = -digit; }
            }
            normalize();
        }

        for (auto& digits : digit_vectors) {
            while (!digits.empty() && digits.back() == 0) { digits.pop_back(); }
        }
        if (digit_vectors[0].size() + digit_vectors[1].size() == 0) {
            digit_vectors[0].push_back(0);
            negative = false;
        }
    }

    std::string to_string() {
        normalize();
        std::string s;
        for (auto digit : digit_vectors[0]) { s += digit_to_char(digit); }
        if (negative) { s += '-'; }
        std::reverse(s.begin(), s.end());
        if (digit_vectors[1].empty()) { return s; }
        s += '.';
        for (auto digit : digit_vectors[1]) { s += digit_to_char(digit); }
        return s;
    }

    friend std::ostream& operator<<(std::ostream& os, BigFloat big_float) {
        return os << big_float.to_string();
    }

    static void align(BigFloat& a, BigFloat& b) {
        for (auto part : {0, 1}) {
            if (a.digit_vectors[part].size() < b.digit_vectors[part].size()) {
                a.digit_vectors[part].resize(b.digit_vectors[part].size());
            } else if (b.digit_vectors[part].size() < a.digit_vectors[part].size()) {
                b.digit_vectors[part].resize(a.digit_vectors[part].size());
            }
        }
    }

    BigFloat operator-() const {
        BigFloat result = *this;
        result.negative = !result.negative;
        return result;
    }

    BigFloat& operator+=(BigFloat other) {
        if ((negative && !other.negative) || (!negative && other.negative)) { return *this -= -other; }
        align(*this, other);
        for (auto part : {0, 1}) {
            for (int i = 0; i < digit_vectors[part].size(); i++) {
                digit_vectors[part][i] += other.digit_vectors[part][i];
            }
        }
        normalize();
        return *this;
    }

    BigFloat& operator-=(BigFloat other) {
        if ((negative && !other.negative) || (!negative && other.negative)) { return *this += -other; }
        align(*this, other);
        for (auto part : {0, 1}) {
            for (int i = 0; i < digit_vectors[part].size(); i++) {
                digit_vectors[part][i] -= other.digit_vectors[part][i];
            }
        }
        normalize();
        return *this;
    }
};

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    int cases;
    std::cin >> cases;
    while (cases--) {
        unsigned short base;
        std::string s1, s2;
        std::cin >> base >> s1 >> s2;

        BigFloat number1(s1, base), number2(s2, base);
        std::clog << number1 << ' ' << number2 << std::endl;
        number1 -= number2;
        std::cout << number1 << std::endl;
    }

    return 0;
}