#252701 (C++14) No.53 悪の漸化式

• 問題: No.53 悪の漸化式
• ユーザー: kei
• 提出日時: 2018-04-20 16:14:16
• 言語: C++14 (gcc 12.3.0 + boost 1.83.0)
• 結果: AC
• 実行時間: 7 ms / 5,000 ms
• コード長: 20,712 bytes
• コンパイル時間: 2,988 ms
• コンパイル使用メモリ: 207,452 KB
• 実行使用メモリ: 5,376 KB
• 最終ジャッジ日時: 2024-06-27 05:06:42
• 合計ジャッジ時間: 3,638 ms
• ジャッジサーバーID （参考情報）: judge1 / judge3

入力	結果	実行時間; 実行使用メモリ
testcase_00	AC	3 ms; 5,248 KB
testcase_01	AC	3 ms; 5,376 KB
testcase_02	AC	3 ms; 5,376 KB
testcase_03	AC	3 ms; 5,376 KB
testcase_04	AC	3 ms; 5,376 KB
testcase_05	AC	3 ms; 5,376 KB
testcase_06	AC	4 ms; 5,376 KB
testcase_07	AC	3 ms; 5,376 KB
testcase_08	AC	3 ms; 5,376 KB
testcase_09	AC	3 ms; 5,376 KB
testcase_10	AC	3 ms; 5,376 KB
testcase_11	AC	4 ms; 5,376 KB
testcase_12	AC	4 ms; 5,376 KB
testcase_13	AC	5 ms; 5,376 KB
testcase_14	AC	5 ms; 5,376 KB
testcase_15	AC	6 ms; 5,376 KB
testcase_16	AC	5 ms; 5,376 KB
testcase_17	AC	6 ms; 5,376 KB
testcase_18	AC	6 ms; 5,376 KB
testcase_19	AC	7 ms; 5,376 KB

ソースコード

#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int INF = 1e9;
const ll LINF = 1e18;
template<class S,class T> ostream& operator << (ostream& out,const pair<S,T>& o){ out << "(" << o.first << "," << o.second << ")"; return out; }
template<class T> ostream& operator << (ostream& out,const vector<T> V){ for(int i = 0; i < V.size(); i++){ out << V[i]; if(i!=V.size()-1) out << " ";} return out; }
template<class T> ostream& operator << (ostream& out,const vector<vector<T> > Mat){ for(int i = 0; i < Mat.size(); i++) { if(i != 0) out << endl; out << Mat[i];} return out; }
template<class S,class T> ostream& operator << (ostream& out,const map<S,T> mp){ out << "{ "; for(auto it = mp.begin(); it != mp.end(); it++){ out << it->first << ":" << it->second; if(mp.size()-1 != distance(mp.begin(),it)) out << ", "; } out << " }"; return out; }

/*
 <url:https://yukicoder.me/problems/no/53>
 問題文============================================================
 以下の漸化式で定義される数列 {Ak}∞k=0 の第 N 項 AN を求めるプログラムを書け。
 　　A0=4,
 　　A1=3,
 　　4Ak=19Ak−1−12Ak−2,k≥2.
 =================================================================
 解説=============================================================
 ================================================================
 */

namespace arithmetic {
    template<typename T> class Addition {
    public:
        template<typename V> T operator+(const V& v) const {
            return T(static_cast<const T&>(*this)) += v;
        }
    };
    
    template<typename T> class Subtraction {
    public:
        template<typename V> T operator-(const V& v) const {
            return T(static_cast<const T&>(*this)) -= v;
        }
    };
    
    template<typename T> class Multiplication {
    public:
        template<typename V> T operator*(const V& v) const {
            return T(static_cast<const T&>(*this)) *= v;
        }
    };
    
    template<typename T> class Division {
    public:
        template<typename V> T operator/(const V& v) const {
            return T(static_cast<const T&>(*this)) /= v;
        }
    };
    
    template<typename T> class Modulus {
    public:
        template<typename V> T operator%(const V& v) const {
            return T(static_cast<const T&>(*this)) %= v;
        }
    };
}

template<typename T> class IndivisibleArithmetic : public arithmetic::Addition<T>, public arithmetic::Subtraction<T>, public arithmetic::Multiplication<T> {};

template<typename T> class Arithmetic : public IndivisibleArithmetic<T>, public arithmetic::Division<T> {};

template<typename T> class Ordered {
public:
    template<typename V> bool operator==(const V& v) const {
        return !(static_cast<T>(v) < static_cast<const T&>(*this) || static_cast<const T&>(*this) < static_cast<T>(v));
    }
    
    template<typename V> bool operator!=(const V& v) const {
        return static_cast<T>(v) < static_cast<const T&>(*this) || static_cast<const T&>(*this) < static_cast<T>(v);
    }
    
    template<typename V> bool operator>(const V& v) const {
        return static_cast<T>(v) < static_cast<const T&>(*this);
    }
    
    template<typename V> bool operator<=(const V& v) const {
        return !(static_cast<T>(v) < static_cast<const T&>(*this));
    }
    
    template<typename V> bool operator>=(const V& v) const {
        return !(static_cast<const T&>(*this) < static_cast<T>(v));
    }
};

template<int IntegerSize = 6, int DecimalSize = 9>
class BigDecimal : public Arithmetic<BigDecimal<IntegerSize, DecimalSize>>, public Ordered<BigDecimal<IntegerSize, DecimalSize>> {
private:
    const static int BitSize = 31;
    const static bool PLUS = false;
    const static bool MINUS = true;
    
    long double EPSILON = pow<long double>(2, -(BitSize - 4) * DecimalSize);
    
    bool sign;
    long long d[IntegerSize + DecimalSize];
    
public:
    BigDecimal() {
        *this = BigDecimal(0);
    }
    
    BigDecimal(int n) {
        sign = PLUS;
        for (auto& i : d) i = 0;
        d[DecimalSize] = n;
        normal();
    }
    
    BigDecimal(long long n) {
        sign = PLUS;
        for (auto& i : d) i = 0;
        d[DecimalSize] = n;
        normal();
    }
    
    BigDecimal(string str) {
        *this = BigDecimal(0);
        bool minus = false;
        if (str[0] == '-') {
            minus = true;
            str = str.substr(1);
        }
        BigDecimal t = 1;
        bool decimal = false;
        for (int i = 0; i < (int)str.size(); ++i) {
            if (str[i] == '.') {
                decimal = true;
            } else {
                if (decimal) *this += (t /= 10) * (str[i] - '0');
                else *this = *this * 10 + (str[i] - '0');
            }
        }
        if (minus) sign = MINUS;
    }
    
    BigDecimal(double r) {
        *this = BigDecimal(0);
        int n;
        BigDecimal b = (r >= 0 ? BigDecimal(1) : BigDecimal(-1));
        r = 2 * abs(frexp(abs(r), &n));
        b <<= n - 1;
        while (r) {
            if (r >= 1) {
                *this += b;
                r -= 1;
            }
            r *= 2;
            b >>= 1;
        }
    }
    
    BigDecimal(long double r) {
        *this = BigDecimal(0);
        int n;
        BigDecimal b = (r >= 0 ? BigDecimal(1) : BigDecimal(-1));
        r = 2 * abs(frexp(abs(r), &n));
        b <<= n - 1;
        while (r) {
            if (r >= 1) {
                *this += b;
                r -= 1;
            }
            r *= 2;
            b >>= 1;
        }
    }
    
    BigDecimal normal() {
        for (int i = 0; i < IntegerSize + DecimalSize - 1; ++i) {
            d[i + 1] += d[i] >> BitSize;
            d[i] &= (1ll << BitSize) - 1;
        }
        if (d[IntegerSize + DecimalSize - 1] < 0) {
            sign = !sign;
            for (int i = 0; i < IntegerSize + DecimalSize; ++i) d[i] = -d[i];
            normal();
        }
        if (d[IntegerSize + DecimalSize - 1] >= (1ll << BitSize)) throw "overflow";
        for (int i = 0; i < IntegerSize + DecimalSize; ++i) if (d[i] != 0) {
            return *this;
        }
        sign = PLUS;
        return *this;
    }
    
    BigDecimal operator-() const {
        BigDecimal bd(*this);
        bd.sign = !bd.sign;
        return bd;
    }
    
    BigDecimal operator<<(int a) const {return BigDecimal(*this) <<= a;}
    BigDecimal operator>>(int a) const {return BigDecimal(*this) >>= a;}
    BigDecimal operator%(const BigDecimal &a) const {return BigDecimal(*this) %= a;}
    
    BigDecimal operator<<=(int a) {
        if (a < 0) return *this >>= -a;
        while (a >= BitSize) {
            if (d[IntegerSize + DecimalSize - 1]) throw "overflow";
            for (int i = IntegerSize + DecimalSize; --i > 0; ) d[i] = d[i - 1];
            d[0] = 0;
            a -= BitSize;
        }
        if (d[IntegerSize + DecimalSize - 1] >= (1ll << (BitSize - a))) throw "overflow";
        for (auto& i : d) i <<= a;
        return normal();
    }
    
    BigDecimal operator>>=(int a) {
        if (a < 0) return *this <<= -a;
        while (a >= BitSize) {
            for (int i = 0; i < IntegerSize + DecimalSize - 1; ++i) d[i] = d[i + 1];
            d[IntegerSize + DecimalSize - 1] >>= BitSize;
            a -= BitSize;
        }
        for (int i = 0; i < IntegerSize + DecimalSize - 1; ++i) {
            d[i] |= d[i + 1] << BitSize;
            d[i + 1] = 0;
        }
        for (auto& i : d) i >>= a;
        return normal();
    }
    
    BigDecimal operator+=(const BigDecimal &a) {
        if (sign == a.sign) for (int i = 0; i < IntegerSize + DecimalSize; ++i) d[i] += a.d[i];
        else for (int i = 0; i < IntegerSize + DecimalSize; ++i) d[i] -= a.d[i];
        return normal();
    }
    
    BigDecimal operator-=(const BigDecimal &a) {
        return *this += -a;
    }
    
    BigDecimal operator*=(const BigDecimal& a) {
        BigDecimal res = 0;
        for (int i = 0; i < IntegerSize + DecimalSize; ++i) {
            if (i < DecimalSize) res = (res + *this * a.d[i]) >> BitSize;
            else res += *this * a.d[i] << (i - DecimalSize) * BitSize;
        }
        res.sign = (sign == a.sign ? PLUS : MINUS);
        return *this = res.normal();
    }
    
    BigDecimal operator*=(const unsigned int& a) {
        for (auto& i : d) i *= a;
        return this->normal();
    }
    
    BigDecimal operator/=(const BigDecimal &a) {
        if (a == 0) throw "divide by zero";
        BigDecimal rev = (double)1 / a.toDouble();
        for (int i = 0; i < 7; ++i) rev = (rev << 1) - a * rev * rev;
        rev.sign = a.sign;
        return *this *= rev;
    }
    
    BigDecimal operator%=(const BigDecimal &a) {
        if (a == 0) throw "modulo by zero";
        return *this -= floor(*this / a) * a;
    }
    
    BigDecimal operator-(const BigDecimal& v) const {
        return BigDecimal(*this) -= v;
    }
    
    BigDecimal operator++() {
        return *this += 1;
    }
    
    BigDecimal operator++(int) {
        BigDecimal bd = *this;
        *this += 1;
        return bd;
    }
    
    BigDecimal operator--() {
        return *this -= 1;
    }
    
    BigDecimal operator--(int) {
        BigDecimal bd = *this;
        *this -= 1;
        return bd;
    }
    
    bool operator<(const BigDecimal &a) const {
        BigDecimal aa = a - EPSILON;
        if (sign == MINUS) {
            if (aa.sign == MINUS) return -a < -*this;
            else return true;
        }
        if (aa.sign == MINUS) return false;
        for (int i = IntegerSize + DecimalSize; i-- > 0; ) if (d[i] != aa.d[i]) return d[i] < aa.d[i];
        return false;
    }
    
    bool equals(const BigDecimal &a) const {
        if (sign != a.sign) return false;
        for (int i = 0; i < IntegerSize + DecimalSize; ++i) if (d[i] != a.d[i]) return false;
        return true;
    }
    
    int toInt() const {
        int res = 0;
        for (int i = 0; i < IntegerSize; ++i) res += d[DecimalSize + i] << BitSize * i;
        if (sign == MINUS) return -res;
        return res;
    }
    
    long long toLongLong() const {
        long long res = 0;
        for (int i = 0; i < IntegerSize; ++i) res += d[DecimalSize + i] << BitSize * i;
        if (sign == MINUS) return -res;
        return res;
    }
    
    string toString(int digit = 100, string mode = "near") const {
        string str;
        BigDecimal a = *this, bd = 1;
        if (a.sign == MINUS) {
            str += "-";
            a.sign = PLUS;
        }
        if (mode == "near") {
            BigDecimal round = BigDecimal(0.5);
            for (int i = 0; i < digit; ++i) round /= 10;
            a += round + EPSILON;
        }
        if (mode == "ceil") {
            BigDecimal round = 1;
            for (int i = 0; i < digit; ++i) round /= 10;
            a += round - EPSILON;
        }
        for (; bd <= a; bd *= 10) ++digit;
        if (bd > 1) {
            bd /= 10;
            --digit;
        }
        for (int i = 0; i < digit + 1; ++i) {
            if (bd == 0) {
                str += "0";
                continue;
            }
            if (bd * 10 == 1) str += ".";
            int d = 0;
            while (bd < a) {
                a -= bd;
                ++d;
            }
            if (d > 9) {
                d -= 10;
                string::iterator itr = str.end();
                while (true) {
                    if (itr == str.begin()) {
                        str = "1" + str;
                        break;
                    }
                    --itr;
                    if (*itr == '.') continue;
                    ++*itr;
                    if (*itr > '9') *itr = '0';
                    else break;
                }
            }
            str += '0' + d;
            bd /= 10;
        }
        return str;
    }
    
    double toDouble() const {
        double res = 0;
        for (int i = 0; i < IntegerSize + DecimalSize; ++i) res += d[i] * pow(2, (i - DecimalSize) * BitSize);
        if (sign == MINUS) return -res;
        return res;
    }
    
    bool isPlus() const {
        return sign == PLUS;
    }
    
    bool isMinus() const {
        return sign == MINUS;
    }
    
    template<int I, int D>
    friend BigDecimal<I, D> pow(const BigDecimal<I, D> &x, const BigDecimal<I, D> &y);
    template<int I, int D>
    friend BigDecimal<I, D> floor(BigDecimal<I, D> x);
};

template<int IntegerSize, int DecimalSize>
BigDecimal<IntegerSize, DecimalSize> pi() {
    const static BigDecimal<IntegerSize, DecimalSize> PI = (atan(BigDecimal<IntegerSize, DecimalSize>(1) / 5) << 4) - (atan(BigDecimal<IntegerSize, DecimalSize>(1) / 239) << 2);
    return PI;
}

template<int IntegerSize, int DecimalSize>
inline BigDecimal<IntegerSize, DecimalSize> operator+(const int& a, BigDecimal<IntegerSize, DecimalSize> b) {
    return BigDecimal<IntegerSize, DecimalSize>(a) + b;
}

template<int IntegerSize, int DecimalSize>
inline BigDecimal<IntegerSize, DecimalSize> operator-(const int& a, BigDecimal<IntegerSize, DecimalSize> b) {
    return BigDecimal<IntegerSize, DecimalSize>(a) - b;
}

template<int IntegerSize, int DecimalSize>
inline BigDecimal<IntegerSize, DecimalSize> operator*(const int& a, BigDecimal<IntegerSize, DecimalSize> b) {
    return BigDecimal<IntegerSize, DecimalSize>(a) * b;
}

template<int IntegerSize, int DecimalSize>
inline BigDecimal<IntegerSize, DecimalSize> operator/(const int& a, BigDecimal<IntegerSize, DecimalSize> b) {
    return BigDecimal<IntegerSize, DecimalSize>(a) / b;
}

template<int IntegerSize, int DecimalSize>
ostream &operator<<(ostream &os, BigDecimal<IntegerSize, DecimalSize> a) {
    os << a.toString(os.precision());
    return os;
}

template<int IntegerSize, int DecimalSize>
istream &operator>>(istream &is, BigDecimal<IntegerSize, DecimalSize> &a) {
    string str;
    is >> str;
    a = BigDecimal<IntegerSize, DecimalSize>(str);
    return is;
}

template<int IntegerSize, int DecimalSize>
BigDecimal<IntegerSize, DecimalSize> sin(BigDecimal<IntegerSize, DecimalSize> x) {
    BigDecimal<IntegerSize, DecimalSize> res = 0, xx = - x * x;
    for (int i = 1; ; i += 2) {
        x /= max(i * (i - 1), 1);
        if (x.equals(0)) break;
        res += x;
        x *= xx;
    }
    return res;
}

template<int IntegerSize, int DecimalSize>
BigDecimal<IntegerSize, DecimalSize> cos(BigDecimal<IntegerSize, DecimalSize> x) {
    BigDecimal<IntegerSize, DecimalSize> res = 0, xx = - x * x;
    x = 1;
    for (int i = 0; ; i += 2) {
        x /= max(i * (i - 1), 1);
        if (x.equals(0)) break;
        res += x;
        x *= xx;
    }
    return res;
}

template<int IntegerSize, int DecimalSize>
BigDecimal<IntegerSize, DecimalSize> tan(const BigDecimal<IntegerSize, DecimalSize> &x) {
    return sin(x) / cos(x);
}

template<int IntegerSize, int DecimalSize>
BigDecimal<IntegerSize, DecimalSize> asin(BigDecimal<IntegerSize, DecimalSize> x) {
    if (abs(x) > 1) throw "out of domain";
    if (x > 1 / sqrt(BigDecimal<IntegerSize, DecimalSize>(2))) return (pi<IntegerSize, DecimalSize>() >> 1) - asin(sqrt(1 - x * x));
    if (x < -1 / sqrt(BigDecimal<IntegerSize, DecimalSize>(2))) return -(pi<IntegerSize, DecimalSize>() >> 1) + asin(sqrt(1 - x * x));
    BigDecimal<IntegerSize, DecimalSize> res = 0, xx = x * x >> 2;
    for (int i = 0; ; ++i) {
        x *= max(i * 2 * (i * 2 - 1), 1);
        x /= max(i * i, 1);
        auto add = x / (i * 2 + 1);
        if (add.equals(0)) break;
        res += add;
        x *= xx;
    }
    return res;
}

template<int IntegerSize, int DecimalSize>
BigDecimal<IntegerSize, DecimalSize> acos(const BigDecimal<IntegerSize, DecimalSize> &x) {
    return (pi<IntegerSize, DecimalSize>() >> 1) - asin(x);
}

template<int IntegerSize, int DecimalSize>
BigDecimal<IntegerSize, DecimalSize> atan(BigDecimal<IntegerSize, DecimalSize> x) {
    if (x.isMinus()) return -atan(-x);
    if (abs(x) > sqrt(2) + 1) return (pi<IntegerSize, DecimalSize>() >> 1) - atan(1 / x);
    if (abs(x) > sqrt(2) - 1) return (pi<IntegerSize, DecimalSize>() >> 2) + atan((x - 1) / (x + 1));
    BigDecimal<IntegerSize, DecimalSize> res = 0, xx = - x * x;
    for (int i = 1; ; i += 2) {
        auto add = x / i;
        if (add.equals(0)) break;
        res += add;
        x *= xx;
    }
    return res;
}

template<int IntegerSize, int DecimalSize>
BigDecimal<IntegerSize, DecimalSize> atan2(const BigDecimal<IntegerSize, DecimalSize> &y, const BigDecimal<IntegerSize, DecimalSize> &x) {
    if (x == 0) {
        if (y > 0) return pi<IntegerSize, DecimalSize>() / 2;
        if (y < 0) return -pi<IntegerSize, DecimalSize>() / 2;
        throw "origin can't define argument";
    }
    if (x.isPlus()) return atan(y / x);
    if (y.isPlus()) return atan(y / x) + pi<IntegerSize, DecimalSize>();
    return atan(y / x) - pi<IntegerSize, DecimalSize>();
}

template<int IntegerSize, int DecimalSize>
BigDecimal<IntegerSize, DecimalSize> sinh(BigDecimal<IntegerSize, DecimalSize> x) {
    BigDecimal<IntegerSize, DecimalSize> res = 0, xx = x * x;
    for (int i = 1; ; i += 2) {
        x /= max(i * (i - 1), 1);
        if (x.equals(0)) break;
        res += x;
        x *= xx;
    }
    return res;
}

template<int IntegerSize, int DecimalSize>
BigDecimal<IntegerSize, DecimalSize> cosh(BigDecimal<IntegerSize, DecimalSize> x) {
    BigDecimal<IntegerSize, DecimalSize> res = 0, xx = x * x;
    x = 1;
    for (int i = 0; ; i += 2) {
        x /= max(i * (i - 1), 1);
        if (x.equals(0)) break;
        res += x;
        x *= xx;
    }
    return res;
}

template<int IntegerSize, int DecimalSize>
BigDecimal<IntegerSize, DecimalSize> tanh(const BigDecimal<IntegerSize, DecimalSize> &x) {return sinh(x) / cosh(x);}

template<int IntegerSize, int DecimalSize>
BigDecimal<IntegerSize, DecimalSize> exp(const BigDecimal<IntegerSize, DecimalSize> &x) {
    BigDecimal<IntegerSize, DecimalSize> res = 0, xx = 1;
    for (int i = 0; ; ++i) {
        xx /= max(i, 1);
        if (xx.equals(0)) break;
        res += xx;
        xx *= x;
    }
    return res;
}

template<int IntegerSize, int DecimalSize>
BigDecimal<IntegerSize, DecimalSize> log(const BigDecimal<IntegerSize, DecimalSize> &x) {
    BigDecimal<IntegerSize, DecimalSize> y = log(x.toDouble());
    BigDecimal<IntegerSize, DecimalSize> z = x / exp(y);
    BigDecimal<IntegerSize, DecimalSize> a = (z - 1) / (z + 1);
    BigDecimal<IntegerSize, DecimalSize> res = 0, b = a, aa = a * a;
    for (int i = 1; ; i += 2) {
        if (b.equals(0)) break;
        res += b / i;
        b *= aa;
    }
    return y + res * 2;
}

template<int IntegerSize, int DecimalSize>
BigDecimal<IntegerSize, DecimalSize> log10(const BigDecimal<IntegerSize, DecimalSize> &x) {
    return log(x) / log(BigDecimal<IntegerSize, DecimalSize>(10));
}

template<int IntegerSize, int DecimalSize>
BigDecimal<IntegerSize, DecimalSize> pow(const BigDecimal<IntegerSize, DecimalSize> &x, const BigDecimal<IntegerSize, DecimalSize> &y) {
    if (x.isMinus()) {
        if (floor(y) == y) return floor(y).d[DecimalSize] % 2 ? -pow(-x, floor(y)) : pow(-x, floor(y));
        throw "power of negative number";
    }
    return exp(y * log(x));
}

template<int IntegerSize, int DecimalSize>
BigDecimal<IntegerSize, DecimalSize> sqrt(const BigDecimal<IntegerSize, DecimalSize> &x) {
    BigDecimal<IntegerSize, DecimalSize> r = 1 / sqrt(x.toDouble());
    for (int i = 0; i < 7; ++i) r *= (3 - x * r * r) >> 1;
    return BigDecimal<IntegerSize, DecimalSize>(1) / r;
}

template<int IntegerSize, int DecimalSize>
BigDecimal<IntegerSize, DecimalSize> abs(const BigDecimal<IntegerSize, DecimalSize> &x) {
    return x.isPlus() ? x : -x;
}

template<int IntegerSize, int DecimalSize>
BigDecimal<IntegerSize, DecimalSize> ceil(const BigDecimal<IntegerSize, DecimalSize> &x) {
    if (x.isMinus()) return -floor(-x);
    auto f = floor(x);
    return f == x ? f : x + 1;
}

template<int IntegerSize, int DecimalSize>
BigDecimal<IntegerSize, DecimalSize> floor(BigDecimal<IntegerSize, DecimalSize> x) {
    if (x.isMinus()) return -ceil(-x);
    x += BigDecimal<IntegerSize, DecimalSize>::EPSILON;
    for (int i = 0; i < DecimalSize; ++i) x.d[i] = 0;
    return x;
}


typedef long double ld;
BigDecimal<> solve(){
    ll N; cin >> N;
    if(N == 0) return BigDecimal<>(4);
    vector<BigDecimal<>> A(N+1);
    A[0] = 4.; A[1] = 3;
    for(int i = 2; i <= N;i++){
        A[i] = (19*A[i-1] - 12*A[i-2])/4.;
    }
    return A[N];
}
int main(void) {
    cin.tie(0); ios_base::sync_with_stdio(false);
    cout << fixed << setprecision(15) << solve() << endl;
    return 0;
}