Задача: 972. Equal Rational Numbers
Сложность: hard

Даны две строки s и t, каждая из которых представляет собой неотрицательное рациональное число. Вернуть true тогда и только тогда, когда они представляют одно и то же число. Строки могут использовать скобки для обозначения повторяющейся части рационального числа.

Рациональное число может быть представлено с использованием до трех частей: <ЦелаяЧасть>, <НеповторяющаясяЧасть> и <ПовторяющаясяЧасть>. Число будет представлено одним из следующих трех способов:

<ЦелаяЧасть>
Например, 12, 0 и 123.
<ЦелаяЧасть><.><НеповторяющаясяЧасть>
Например, 0.5, 1., 2.12 и 123.0001.
<ЦелаяЧасть><.><НеповторяющаясяЧасть><(><ПовторяющаясяЧасть><)>
Например, 0.1(6), 1.(9), 123.00(1212).
Повторяющаяся часть десятичного разложения обозначается в круглых скобках. Например:

1/6 = 0.16666666... = 0.1(6) = 0.1666(6) = 0.166(66).

Пример:

Input: s = "0.(52)", t = "0.5(25)"
Output: true
Explanation: Because "0.(52)" represents 0.52525252..., and "0.5(25)" represents 0.52525252525..... , the strings represent the same number.

👨‍💻 Алгоритм:

1⃣Преобразование дроби. Определите и изолируйте повторяющуюся часть дроби. Преобразуйте строку, представляющую число, в выражение вида S=x/(10^k-1), где x — повторяющаяся часть, а k — её длина.

2⃣Вычисление геометрической суммы. Преобразуйте повторяющуюся часть в сумму вида S=x*(r/(1-r)), где r = 10^(-k). Найдите значение дроби для повторяющейся части, используя формулу геометрической прогрессии.

3⃣Обработка неповторяющейся части. Определите значение неповторяющейся части дроби как обычное число. Объедините результаты для повторяющейся и неповторяющейся частей для получения итогового значения.

😎 Решение:

class Fraction {
public:
    long n, d;

    Fraction(long n, long d) {
        long g = gcd(n, d);
        this->n = n / g;
        this->d = d / g;
    }

    void iadd(const Fraction& other) {
        long numerator = this->n * other.d + this->d * other.n;
        long denominator = this->d * other.d;
        long g = gcd(numerator, denominator);
        this->n = numerator / g;
        this->d = denominator / g;
    }

    static long gcd(long x, long y) {
        return x != 0 ? gcd(y % x, x) : y;
    }
};

class Solution {
public:
    bool isRationalEqual(string S, string T) {
        Fraction f1 = convert(S);
        Fraction f2 = convert(T);
        return f1.n == f2.n && f1.d == f2.d;
    }

    Fraction convert(string S) {
        int state = 0;
        Fraction ans(0, 1);
        int decimal_size = 0;
        vector<string> parts = split(S, ".()");

        for (string& part : parts) {
            state++;
            if (part.empty()) continue;
            long x = stol(part);
            int sz = part.length();

            if (state == 1) {
                ans.iadd(Fraction(x, 1));
            } else if (state == 2) {
                ans.iadd(Fraction(x, pow(10, sz)));
                decimal_size = sz;
            } else {
                long denom = pow(10, decimal_size);
                denom *= pow(10, sz) - 1;
                ans.iadd(Fraction(x, denom));
            }
        }
        return ans;
    }

private:
    vector<string> split(const string& s, const string& delimiters) {
        vector<string> tokens;
        size_t start = 0;
        size_t end = s.find_first_of(delimiters);
        while (end != string::npos) {
            if (end > start)
                tokens.push_back(s.substr(start, end - start));
            start = end + 1;
            end = s.find

Ставь 👍 и забирай 📚 Базу знаний