結果
| 問題 | No.1230 Hall_and_me |
| ユーザー |
 kotamanegi
|
| 提出日時 | 2020-09-18 21:25:14 |
| 言語 | C++17(clang) (17.0.6 + boost 1.87.0) |
| 結果 |
AC
|
| 実行時間 | 2 ms / 2,000 ms |
| コード長 | 24,576 bytes |
| コンパイル時間 | 4,122 ms |
| コンパイル使用メモリ | 171,904 KB |
| 実行使用メモリ | 6,944 KB |
| 最終ジャッジ日時 | 2024-06-22 08:43:50 |
| 合計ジャッジ時間 | 5,213 ms |
|
ジャッジサーバーID （参考情報） |
judge5 / judge1 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 2 |
| other | AC * 36 |
コンパイルメッセージ
main.cpp:9:18: warning: '#pragma comment linker' ignored [-Wignored-pragmas]
9 | #pragma comment (linker, "/STACK:526000000")
| ^
1 warning generated.
ソースコード
//shiawase wa yukkuri hajimaru.#define _CRT_SECURE_NO_WARNINGS#define _USE_MATH_DEFINES#define _SILENCE_ALL_CXX17_DEPRECATION_WARNINGS#pragma GCC target("avx2")#pragma GCC optimize("O3")#pragma GCC optimize("unroll-loops")#pragma comment (linker, "/STACK:526000000")#include "bits/stdc++.h"#ifndef ATCODER_MODINT_HPP#define ATCODER_MODINT_HPP 1#ifndef ATCODER_INTERNAL_MATH_HPP#define ATCODER_INTERNAL_MATH_HPP 1#include <utility>namespace atcoder {namespace internal {// @param m `1 <= m`// @return x mod mconstexpr long long safe_mod(long long x, long long m) {x %= m;if (x < 0) x += m;return x;}// Fast moduler by barrett reduction// Reference: https://en.wikipedia.org/wiki/Barrett_reduction// NOTE: reconsider after Ice Lakestruct barrett {unsigned int _m;unsigned long long im;// @param m `1 <= m`barrett(unsigned int m) : _m(m), im((unsigned long long)(-1) / m + 1) {}// @return munsigned int umod() const { return _m; }// @param a `0 <= a < m`// @param b `0 <= b < m`// @return `a * b % m`unsigned int mul(unsigned int a, unsigned int b) const {// [1] m = 1// a = b = im = 0, so okay// [2] m >= 2// im = ceil(2^64 / m)// -> im * m = 2^64 + r (0 <= r < m)// let z = a*b = c*m + d (0 <= c, d < m)// a*b * im = (c*m + d) * im = c*(im*m) + d*im = c*2^64 + c*r + d*im// c*r + d*im < m * m + m * im < m * m + 2^64 + m <= 2^64 + m * (m + 1) < 2^64 * 2// ((ab * im) >> 64) == c or c + 1unsigned long long z = a;z *= b;#ifdef _MSC_VERunsigned long long x;_umul128(z, im, &x);#elseunsigned long long x =(unsigned long long)(((unsigned __int128)(z)*im) >> 64);#endifunsigned int v = (unsigned int)(z - x * _m);if (_m <= v) v += _m;return v;}};// @param n `0 <= n`// @param m `1 <= m`// @return `(x ** n) % m`constexpr long long pow_mod_constexpr(long long x, long long n, int m) {if (m == 1) return 0;unsigned int _m = (unsigned int)(m);unsigned long long r = 1;unsigned long long y = safe_mod(x, m);while (n) {if (n & 1) r = (r * y) % _m;y = (y * y) % _m;n >>= 1;}return r;}// Reference:// M. Forisek and J. Jancina,// Fast Primality Testing for Integers That Fit into a Machine Word// @param n `0 <= n`constexpr bool is_prime_constexpr(int n) {if (n <= 1) return false;if (n == 2 || n == 7 || n == 61) return true;if (n % 2 == 0) return false;long long d = n - 1;while (d % 2 == 0) d /= 2;int vs[3] = { 2,7,61 };for (long long a : vs) {long long t = d;long long y = pow_mod_constexpr(a, t, n);while (t != n - 1 && y != 1 && y != n - 1) {y = y * y % n;t <<= 1;}if (y != n - 1 && t % 2 == 0) {return false;}}return true;}template <int n> constexpr bool is_prime = is_prime_constexpr(n);// @param b `1 <= b`// @return pair(g, x) s.t. g = gcd(a, b), xa = g (mod b), 0 <= x < b/gconstexpr std::pair<long long, long long> inv_gcd(long long a, long long b) {a = safe_mod(a, b);if (a == 0) return { b, 0 };// Contracts:// [1] s - m0 * a = 0 (mod b)// [2] t - m1 * a = 0 (mod b)// [3] s * |m1| + t * |m0| <= blong long s = b, t = a;long long m0 = 0, m1 = 1;while (t) {long long u = s / t;s -= t * u;m0 -= m1 * u; // |m1 * u| <= |m1| * s <= b// [3]:// (s - t * u) * |m1| + t * |m0 - m1 * u|// <= s * |m1| - t * u * |m1| + t * (|m0| + |m1| * u)// = s * |m1| + t * |m0| <= bauto tmp = s;s = t;t = tmp;tmp = m0;m0 = m1;m1 = tmp;}// by [3]: |m0| <= b/g// by g != b: |m0| < b/gif (m0 < 0) m0 += b / s;return { s, m0 };}// Compile time primitive root// @param m must be prime// @return primitive root (and minimum in now)constexpr int primitive_root_constexpr(int m) {if (m == 2) return 1;if (m == 167772161) return 3;if (m == 469762049) return 3;if (m == 754974721) return 11;if (m == 998244353) return 3;int divs[20] = {};divs[0] = 2;int cnt = 1;int x = (m - 1) / 2;while (x % 2 == 0) x /= 2;for (int i = 3; (long long)(i)*i <= x; i += 2) {if (x % i == 0) {divs[cnt++] = i;while (x % i == 0) {x /= i;}}}if (x > 1) {divs[cnt++] = x;}for (int g = 2;; g++) {bool ok = true;for (int i = 0; i < cnt; i++) {if (pow_mod_constexpr(g, (m - 1) / divs[i], m) == 1) {ok = false;break;}}if (ok) return g;}}template <int m> constexpr int primitive_root = primitive_root_constexpr(m);} // namespace internal} // namespace atcoder#endif // ATCODER_INTERNAL_MATH_HPP#ifndef ATCODER_INTERNAL_TYPE_TRAITS_HPP#define ATCODER_INTERNAL_TYPE_TRAITS_HPP 1#include <cassert>#include <numeric>#include <type_traits>namespace atcoder {namespace internal {#ifndef _MSC_VERtemplate <class T>using is_signed_int128 =typename std::conditional<std::is_same<T, __int128_t>::value ||std::is_same<T, __int128>::value,std::true_type,std::false_type>::type;template <class T>using is_unsigned_int128 =typename std::conditional<std::is_same<T, __uint128_t>::value ||std::is_same<T, unsigned __int128>::value,std::true_type,std::false_type>::type;template <class T>using make_unsigned_int128 =typename std::conditional<std::is_same<T, __int128_t>::value,__uint128_t,unsigned __int128>;template <class T>using is_integral = typename std::conditional<std::is_integral<T>::value ||is_signed_int128<T>::value ||is_unsigned_int128<T>::value,std::true_type,std::false_type>::type;template <class T>using is_signed_int = typename std::conditional<(is_integral<T>::value&&std::is_signed<T>::value) ||is_signed_int128<T>::value,std::true_type,std::false_type>::type;template <class T>using is_unsigned_int =typename std::conditional<(is_integral<T>::value&&std::is_unsigned<T>::value) ||is_unsigned_int128<T>::value,std::true_type,std::false_type>::type;template <class T>using to_unsigned = typename std::conditional<is_signed_int128<T>::value,make_unsigned_int128<T>,typename std::conditional<std::is_signed<T>::value,std::make_unsigned<T>,std::common_type<T>>::type>::type;#elsetemplate <class T> using is_integral = typename std::is_integral<T>;template <class T>using is_signed_int =typename std::conditional<is_integral<T>::value&& std::is_signed<T>::value,std::true_type,std::false_type>::type;template <class T>using is_unsigned_int =typename std::conditional<is_integral<T>::value&&std::is_unsigned<T>::value,std::true_type,std::false_type>::type;template <class T>using to_unsigned = typename std::conditional<is_signed_int<T>::value,std::make_unsigned<T>,std::common_type<T>>::type;#endiftemplate <class T>using is_signed_int_t = std::enable_if_t<is_signed_int<T>::value>;template <class T>using is_unsigned_int_t = std::enable_if_t<is_unsigned_int<T>::value>;template <class T> using to_unsigned_t = typename to_unsigned<T>::type;} // namespace internal} // namespace atcoder#endif // ATCODER_INTERNAL_TYPE_TRAITS_HPP#include <cassert>#include <numeric>#include <type_traits>#ifdef _MSC_VER#include <intrin.h>#endifnamespace atcoder {namespace internal {struct modint_base {};struct static_modint_base : modint_base {};template <class T> using is_modint = std::is_base_of<modint_base, T>;template <class T> using is_modint_t = std::enable_if_t<is_modint<T>::value>;} // namespace internaltemplate <int m, std::enable_if_t<(1 <= m)>* = nullptr>struct static_modint : internal::static_modint_base {using mint = static_modint;public:static constexpr int mod() { return m; }static mint raw(int v) {mint x;x._v = v;return x;}static_modint() : _v(0) {}template <class T, internal::is_signed_int_t<T>* = nullptr>static_modint(T v) {long long x = (long long)(v % (long long)(umod()));if (x < 0) x += umod();_v = (unsigned int)(x);}template <class T, internal::is_unsigned_int_t<T>* = nullptr>static_modint(T v) {_v = (unsigned int)(v % umod());}static_modint(bool v) { _v = ((unsigned int)(v) % umod()); }unsigned int val() const { return _v; }mint& operator++() {_v++;if (_v == umod()) _v = 0;return *this;}mint& operator--() {if (_v == 0) _v = umod();_v--;return *this;}mint operator++(int) {mint result = *this;++* this;return result;}mint operator--(int) {mint result = *this;--* this;return result;}mint& operator+=(const mint& rhs) {_v += rhs._v;if (_v >= umod()) _v -= umod();return *this;}mint& operator-=(const mint& rhs) {_v -= rhs._v;if (_v >= umod()) _v += umod();return *this;}mint& operator*=(const mint& rhs) {unsigned long long z = _v;z *= rhs._v;_v = (unsigned int)(z % umod());return *this;}mint& operator/=(const mint& rhs) { return *this = *this * rhs.inv(); }mint operator+() const { return *this; }mint operator-() const { return mint() - *this; }mint pow(long long n) const {assert(0 <= n);mint x = *this, r = 1;while (n) {if (n & 1) r *= x;x *= x;n >>= 1;}return r;}mint inv() const {if (prime) {assert(_v);return pow(umod() - 2);}else {auto eg = internal::inv_gcd(_v, m);assert(eg.first == 1);return eg.second;}}friend mint operator+(const mint& lhs, const mint& rhs) {return mint(lhs) += rhs;}friend mint operator-(const mint& lhs, const mint& rhs) {return mint(lhs) -= rhs;}friend mint operator*(const mint& lhs, const mint& rhs) {return mint(lhs) *= rhs;}friend mint operator/(const mint& lhs, const mint& rhs) {return mint(lhs) /= rhs;}friend bool operator==(const mint& lhs, const mint& rhs) {return lhs._v == rhs._v;}friend bool operator!=(const mint& lhs, const mint& rhs) {return lhs._v != rhs._v;}private:unsigned int _v;static constexpr unsigned int umod() { return m; }static constexpr bool prime = internal::is_prime<m>;};template <int id> struct dynamic_modint : internal::modint_base {using mint = dynamic_modint;public:static int mod() { return (int)(bt.umod()); }static void set_mod(int m) {assert(1 <= m);bt = internal::barrett(m);}static mint raw(int v) {mint x;x._v = v;return x;}dynamic_modint() : _v(0) {}template <class T, internal::is_signed_int_t<T>* = nullptr>dynamic_modint(T v) {long long x = (long long)(v % (long long)(mod()));if (x < 0) x += mod();_v = (unsigned int)(x);}template <class T, internal::is_unsigned_int_t<T>* = nullptr>dynamic_modint(T v) {_v = (unsigned int)(v % mod());}dynamic_modint(bool v) { _v = ((unsigned int)(v) % mod()); }unsigned int val() const { return _v; }mint& operator++() {_v++;if (_v == umod()) _v = 0;return *this;}mint& operator--() {if (_v == 0) _v = umod();_v--;return *this;}mint operator++(int) {mint result = *this;++* this;return result;}mint operator--(int) {mint result = *this;--* this;return result;}mint& operator+=(const mint& rhs) {_v += rhs._v;if (_v >= umod()) _v -= umod();return *this;}mint& operator-=(const mint& rhs) {_v += mod() - rhs._v;if (_v >= umod()) _v -= umod();return *this;}mint& operator*=(const mint& rhs) {_v = bt.mul(_v, rhs._v);return *this;}mint& operator/=(const mint& rhs) { return *this = *this * rhs.inv(); }mint operator+() const { return *this; }mint operator-() const { return mint() - *this; }mint pow(long long n) const {assert(0 <= n);mint x = *this, r = 1;while (n) {if (n & 1) r *= x;x *= x;n >>= 1;}return r;}mint inv() const {auto eg = internal::inv_gcd(_v, mod());assert(eg.first == 1);return eg.second;}friend mint operator+(const mint& lhs, const mint& rhs) {return mint(lhs) += rhs;}friend mint operator-(const mint& lhs, const mint& rhs) {return mint(lhs) -= rhs;}friend mint operator*(const mint& lhs, const mint& rhs) {return mint(lhs) *= rhs;}friend mint operator/(const mint& lhs, const mint& rhs) {return mint(lhs) /= rhs;}friend bool operator==(const mint& lhs, const mint& rhs) {return lhs._v == rhs._v;}friend bool operator!=(const mint& lhs, const mint& rhs) {return lhs._v != rhs._v;}private:unsigned int _v;static internal::barrett bt;static unsigned int umod() { return bt.umod(); }};template <int id> internal::barrett dynamic_modint<id>::bt = 998244353;using modint998244353 = static_modint<998244353>;using modint1000000007 = static_modint<1000000007>;using modint = dynamic_modint<-1>;namespace internal {template <class T>using is_static_modint = std::is_base_of<internal::static_modint_base, T>;template <class T>using is_static_modint_t = std::enable_if_t<is_static_modint<T>::value>;template <class> struct is_dynamic_modint : public std::false_type {};template <int id>struct is_dynamic_modint<dynamic_modint<id>> : public std::true_type {};template <class T>using is_dynamic_modint_t = std::enable_if_t<is_dynamic_modint<T>::value>;} // namespace internal} // namespace atcoder#endif // ATCODER_MODINT_HPP#define int llusing namespace std;typedef string::const_iterator State;#define eps 1e-8L#define MAX_MOD 1000000007LL#define GYAKU 500000004LL#define MOD 998244353LL#define pb push_back#define mp make_pairtypedef long long ll;typedef long double ld;#define REP(a,b) for(long long (a) = 0;(a) < (b);++(a))#define ALL(x) (x).begin(),(x).end()unsigned long xor128() {static unsigned long x = 123456789, y = 362436069, z = 521288629, w = 88675123;unsigned long t = (x ^ (x << 11));x = y; y = z; z = w;return (w = (w ^ (w >> 19)) ^ (t ^ (t >> 8)));};typedef complex<long double> Point;typedef pair<complex<long double>, complex<long double>> Line;typedef struct Circle {complex<long double> center;long double r;}Circle;long double dot(Point a, Point b) {return (a.real() * b.real() + a.imag() * b.imag());}long double cross(Point a, Point b) {return (a.real() * b.imag() - a.imag() * b.real());}long double Dist_Line_Point(Line a, Point b) {if (dot(a.second - a.first, b - a.first) < eps) return abs(b - a.first);if (dot(a.first - a.second, b - a.second) < eps) return abs(b - a.second);return abs(cross(a.second - a.first, b - a.first)) / abs(a.second - a.first);}int is_intersected_ls(Line a, Line b) {return (cross(a.second - a.first, b.first - a.first) * cross(a.second - a.first, b.second - a.first) < eps) &&(cross(b.second - b.first, a.first - b.first) * cross(b.second - b.first, a.second - b.first) < eps);}Point intersection_l(Line a, Line b) {Point da = a.second - a.first;Point db = b.second - b.first;return a.first + da * cross(db, b.first - a.first) / cross(db, da);}long double Dist_Line_Line(Line a, Line b) {if (is_intersected_ls(a, b) == 1) {return 0;}return min({ Dist_Line_Point(a,b.first), Dist_Line_Point(a,b.second),Dist_Line_Point(b,a.first),Dist_Line_Point(b,a.second) });}pair<Point, Point> intersection_Circle_Circle(Circle a, Circle b) {long double dist = abs(a.center - b.center);assert(dist <= eps + a.r + b.r);assert(dist + eps >= abs(a.r - b.r));Point target = b.center - a.center;long double pointer = target.real() * target.real() + target.imag() * target.imag();long double aa = pointer + a.r * a.r - b.r * b.r;aa /= 2.0L;Point l{ (aa * target.real() + target.imag() * sqrt(pointer * a.r * a.r - aa * aa)) / pointer,(aa * target.imag() - target.real() * sqrt(pointer * a.r * a.r - aa * aa)) / pointer };Point r{ (aa * target.real() - target.imag() * sqrt(pointer * a.r * a.r - aa * aa)) / pointer,(aa * target.imag() + target.real() * sqrt(pointer * a.r * a.r - aa * aa)) / pointer };r = r + a.center;l = l + a.center;return mp(l, r);}ll gcd(ll a, ll b) {if (b == 0) return a;return gcd(b, a % b);}template<typename A>A pows(A val, ll b) {assert(b >= 1);A ans = val;b--;while (b) {if (b % 2) {ans *= val;}val *= val;b /= 2LL;}return ans;}template<typename A>class Compressor {public:bool is_zipped = false;map<A, ll> zipper;map<ll, A> unzipper;queue<A> fetcher;Compressor() {is_zipped = false;zipper.clear();unzipper.clear();}void add(A now) {assert(is_zipped == false);zipper[now] = 1;fetcher.push(now);}void exec() {assert(is_zipped == false);int cnt = 0;for (auto i = zipper.begin(); i != zipper.end(); ++i) {i->second = cnt;unzipper[cnt] = i->first;cnt++;}is_zipped = true;}ll fetch() {assert(is_zipped == true);A hoge = fetcher.front();fetcher.pop();return zipper[hoge];}ll zip(A now) {assert(is_zipped == true);assert(zipper.find(now) != zipper.end());return zipper[now];}A unzip(ll a) {assert(is_zipped == true);assert(a < unzipper.size());return unzipper[a];}ll next(A now) {auto x = zipper.upper_bound(now);if (x == zipper.end()) return zipper.size();return (ll)((*x).second);}ll back(A now) {auto x = zipper.lower_bound(now);if (x == zipper.begin()) return -1;x--;return (ll)((*x).second);}};template<typename A>class Matrix {public:vector<vector<A>> data;Matrix(vector<vector<A>> a) :data(a) {}Matrix operator + (const Matrix obj) {vector<vector<A>> ans;assert(obj.data.size() == this->data.size());assert(obj.data[0].size() == this->data[0].size());REP(i, obj.data.size()) {ans.push_back(vector<A>());REP(q, obj.data[i].size()) {A hoge = obj.data[i][q] + (this->data[i][q]);ans.back().push_back(hoge);}}return Matrix(ans);}Matrix operator - (const Matrix obj) {vector<vector<A>> ans;assert(obj.data.size() == this->data.size());assert(obj.data[0].size() == this->data[0].size());REP(i, obj.data.size()) {ans.push_back(vector<A>());REP(q, obj.data[i].size()) {A hoge = this->data[i][q] - obj.data[i][q];ans.back().push_back(hoge);}}return Matrix(ans);}Matrix operator * (const Matrix obj) {vector<vector<A>> ans;assert(obj.data.size() == this->data[0].size());REP(i, this -> data.size()) {ans.push_back(vector<A>());REP(q, obj.data[0].size()) {A hoge = ((this->data[i][0]) * (obj.data[0][q]));for (int t = 1; t < obj.data.size(); ++t) {hoge += ((this->data[i][t]) * obj.data[t][q]);}ans.back().push_back(hoge);}}return Matrix(ans);}Matrix& operator *= (const Matrix obj) {*this = (*this * obj);return *this;}Matrix& operator += (const Matrix obj) {*this = (*this + obj);return *this;}Matrix& operator -= (const Matrix obj) {*this = (*this - obj);return *this;}};struct Fraction {ll a;ll b;Fraction() :a(0LL), b(1LL) {}Fraction(ll c, ll d) {int hoge = gcd(llabs(c), llabs(d));if (hoge != 0) {c /= hoge;d /= hoge;if (d < 0 or (d == 0 and c < 0)) {d *= -1;c *= -1;}}a = c;b = d;}bool operator <(Fraction rhs) const {if (a < 0 and rhs.a > 0) return 1;if (a > 0 and rhs.a < 0) return 0;return a * rhs.b < rhs.a* b;}bool operator ==(Fraction rhs) const {return a == rhs.a and b == rhs.b;}};class Dice {public:vector<ll> vertexs;Dice(vector<ll> init) :vertexs(init) {}void RtoL() {for (int q = 1; q < 4; ++q) {swap(vertexs[q], vertexs[q + 1]);}}void LtoR() {for (int q = 3; q >= 1; --q) {swap(vertexs[q], vertexs[q + 1]);}}void UtoD() {swap(vertexs[5], vertexs[4]);swap(vertexs[2], vertexs[5]);swap(vertexs[0], vertexs[2]);}void DtoU() {swap(vertexs[0], vertexs[2]);swap(vertexs[2], vertexs[5]);swap(vertexs[5], vertexs[4]);}bool ReachAble(Dice now) {set<Dice> hoge;queue<Dice> next;next.push(now);hoge.insert(now);while (next.empty() == false) {Dice seeing = next.front();next.pop();if (seeing == *this) return true;seeing.RtoL();if (hoge.count(seeing) == 0) {hoge.insert(seeing);next.push(seeing);}seeing.LtoR();seeing.LtoR();if (hoge.count(seeing) == 0) {hoge.insert(seeing);next.push(seeing);}seeing.RtoL();seeing.UtoD();if (hoge.count(seeing) == 0) {hoge.insert(seeing);next.push(seeing);}seeing.DtoU();seeing.DtoU();if (hoge.count(seeing) == 0) {hoge.insert(seeing);next.push(seeing);}}return false;}bool operator ==(const Dice& a) {for (int q = 0; q < 6; ++q) {if (a.vertexs[q] != (*this).vertexs[q]) {return false;}}return true;}bool operator <(const Dice& a) const {return (*this).vertexs < a.vertexs;}};pair<Dice, Dice> TwoDimDice(int center, int up) {int target = 1;while (true) {if (center != target && 7 - center != target && up != target && 7 - up != target) {break;}target++;}return mp(Dice(vector<ll>{up, target, center, 7 - target, 7 - center, 7 - up}), Dice(vector<ll>{up, 7 - target, center, target, 7 - center, 7 -up}));}tuple<Dice, Dice, Dice, Dice> OneDimDice(int center) {int bo = min(center, 7 - center);pair<int, int> goa;if (bo == 1) {goa = mp(2, 3);}else if (bo == 2) {goa = mp(1, 3);}else if (bo == 3) {goa = mp(1, 2);}tuple<Dice, Dice, Dice, Dice> now = make_tuple(Dice(vector<ll>{goa.first, goa.second, center, 7 - goa.second, 7 - center, 7 - goa.first}),Dice(vector<ll>{goa.first, 7 - goa.second, center, goa.second, 7 - center, 7 - goa.first}),Dice(vector<ll>{7 - goa.first, goa.second, center, 7 - goa.second, 7 - center, goa.first}),Dice(vector<ll>{7 - goa.first, 7 - goa.second, center, goa.second, 7 - center, goa.first}));return now;}class HLDecomposition {public:vector<vector<int>> vertexs;vector<int> depth;vector<int> backs;vector<int> connections;vector<int> zip, unzip;HLDecomposition(int n) {vertexs = vector<vector<int>>(n, vector<int>());depth = vector<int>(n);zip = vector<int>(n);unzip = zip;}void add_edge(int a, int b) {vertexs[a].push_back(b);vertexs[b].push_back(a);}int depth_dfs(int now, int back) {depth[now] = 0;for (auto x : vertexs[now]) {if (x == back) continue;depth[now] = max(depth[now], 1 + depth_dfs(x, now));}return depth[now];}void dfs(int now, int backing) {zip[now] = backs.size();unzip[backs.size()] = now;backs.push_back(backing);int now_max = -1;int itr = -1;for (auto x : vertexs[now]) {if (depth[x] > depth[now]) continue;if (now_max < depth[x]) {now_max = depth[x];itr = x;}}if (itr == -1) return;connections.push_back(connections.back());dfs(itr, backing);for (auto x : vertexs[now]) {if (depth[x] > depth[now]) continue;if (x == itr) continue;connections.push_back(zip[now]);dfs(x, backs.size());}return;}void build() {depth_dfs(0, -1);connections.push_back(-1);dfs(0, -1);}vector<pair<int, int>> query(int a, int b) {a = zip[a];b = zip[b];vector<pair<int, int>> ans;while (backs[a] != backs[b]) {if (a < b) swap(a, b);ans.push_back(mp(backs[a], a + 1));a = connections[a];}if (a > b) swap(a, b);ans.push_back(mp(a, b + 1));return ans;}int lca(int a, int b) {a = zip[a];b = zip[b];while (backs[a] != backs[b]) {if (a < b) swap(a, b);a = connections[a];}return unzip[min(a, b)];}};void init() {iostream::sync_with_stdio(false);cout << fixed << setprecision(50);}using namespace atcoder;#define int llvoid solve(){vector<ld> inputs;REP(i, 3) {ld a;cin >> a;inputs.push_back(a);}sort(ALL(inputs));ld ans = -1;ld bunbo = inputs[0] + inputs[1] + inputs[2];do {ld tmp = (inputs[1] + inputs[2]) / bunbo;ans = max(ans, tmp);} while (next_permutation(ALL(inputs)));cout << ans << endl;}#undef intint main() {init();int t = 1;REP(tea, t) {solve();}}