#include #define REP_(i, a_, b_, a, b, ...) \ for (int i = (a), END_##i = (b); i < END_##i; ++i) #define REP(i, ...) REP_(i, __VA_ARGS__, __VA_ARGS__, 0, __VA_ARGS__) #define ALL(x) std::begin(x), std::end(x) using Int = long long; using Real = long double; template inline bool chmax(T &a, U b) { return a < b and ((a = std::move(b)), true); } template inline bool chmin(T &a, U b) { return a > b and ((a = std::move(b)), true); } template inline int ssize(const T &a) { return (int) a.size(); } template inline std::ostream &print_one(const T &x, char endc) { if constexpr (std::is_same_v) { return std::cout << (x ? "Yes" : "No") << endc; } else { return std::cout << x << endc; } } template inline std::ostream &print(const T &x) { return print_one(x, '\n'); } template std::ostream &print(const T &head, Ts... tail) { return print_one(head, ' '), print(tail...); } inline std::ostream &print() { return std::cout << '\n'; } template std::ostream &print_seq(const Container &a, std::string_view sep = " ", std::string_view ends = "\n", std::ostream &os = std::cout) { auto b = std::begin(a), e = std::end(a); for (auto it = std::begin(a); it != e; ++it) { if (it != b) os << sep; os << *it; } return os << ends; } template struct is_iterable : std::false_type {}; template struct is_iterable())), decltype(std::end(std::declval()))>> : std::true_type { }; template::value && !std::is_same::value>> std::ostream &operator<<(std::ostream &os, const T &a) { return print_seq(a, ", ", "", (os << "{")) << "}"; } struct CastInput { template operator T() const { T x; std::cin >> x; return x; } struct Sized { std::size_t n; template operator T() const { T x(n); for (auto &e: x) std::cin >> e; return x; } }; Sized operator()(std::size_t n) const { return {n}; } } const in; inline void check(bool cond, const char *message = "!ERROR!") { if (not cond) throw std::runtime_error(message); } #ifdef MY_DEBUG #include "debug_dump.hpp" #else #define DUMP(...) #define cerr if(false)std::cerr #endif using namespace std; template struct NaiveMult { using value_type = T; static constexpr int dmax() { return DMAX; } static std::vector multiply(const std::vector &x, const std::vector &y) { const int n = std::min(x.size() + y.size() - 1, DMAX + 1); const int mi = std::min(x.size(), n); std::vector res(n); for (int i = 0; i < mi; ++i) { for (int j = 0; j < int(y.size()); ++j) { if (i + j >= n) break; res[i + j] += x[i] * y[j]; } } return res; } static std::vector invert(const std::vector &x) { std::vector res(DMAX + 1); res[0] = x[0].inv(); for (int i = 1; i <= DMAX; ++i) { T s = 0; const int mj = std::min(i + 1, x.size()); for (int j = 1; j < mj; ++j) { s += x[j] * res[i - j]; } res[i] = -res[0] * s; } return res; } }; // Formal Power Series (dense format). template struct DenseFPS { using T = typename Mult::value_type; static constexpr int dmax() { return Mult::dmax(); } // Coefficients of terms from x^0 to x^DMAX. std::vector coeff_; DenseFPS() : coeff_(1, 0) {} // = 0 * x^0 explicit DenseFPS(std::vector c) : coeff_(std::move(c)) { while (size() > dmax() + 1) coeff_.pop_back(); assert(size() > 0); } DenseFPS(std::initializer_list init) : coeff_(init.begin(), init.end()) { while (size() > dmax() + 1) coeff_.pop_back(); assert(size() > 0); } DenseFPS(const DenseFPS &other) : coeff_(other.coeff_) {} DenseFPS(DenseFPS &&other) : coeff_(std::move(other.coeff_)) {} DenseFPS &operator=(const DenseFPS &other) { coeff_ = other.coeff_; return *this; } DenseFPS &operator=(DenseFPS &&other) { coeff_ = std::move(other.coeff_); return *this; } // size <= dmax + 1 inline int size() const { return static_cast(coeff_.size()); } // Returns the coefficient of x^k. inline T operator[](int k) const { return (k >= size()) ? 0 : coeff_[k]; } DenseFPS &operator+=(const T &scalar) { coeff_[0] += scalar; return *this; } friend DenseFPS operator+(const DenseFPS &f, const T &scalar) { return DenseFPS(f) += scalar; } DenseFPS &operator+=(const DenseFPS &other) { if (size() < other.size()) coeff_.resize(other.size()); for (int i = 0; i < other.size(); ++i) coeff_[i] += other[i]; return *this; } friend DenseFPS operator+(const DenseFPS &f, const DenseFPS &g) { return DenseFPS(f) += g; } DenseFPS &operator-=(const DenseFPS &other) { if (size() < other.size()) coeff_.resize(other.size()); for (int i = 0; i < other.size(); ++i) coeff_[i] -= other[i]; return *this; } friend DenseFPS operator-(const DenseFPS &f, const DenseFPS &g) { return DenseFPS(f) -= g; } DenseFPS operator-() const { return *this * -1; } DenseFPS &operator*=(const T &scalar) { for (auto &x: coeff_) x *= scalar; return *this; } friend DenseFPS operator*(const DenseFPS &f, const T &scalar) { return DenseFPS(f) *= scalar; } friend DenseFPS operator*(const T &scalar, const DenseFPS &g) { return DenseFPS{scalar} *= g; } DenseFPS &operator*=(const DenseFPS &other) { return *this = DenseFPS(Mult::multiply(std::move(this->coeff_), other.coeff_)); } friend DenseFPS operator*(const DenseFPS &f, const DenseFPS &g) { return DenseFPS(Mult::multiply(f.coeff_, g.coeff_)); } DenseFPS &operator/=(const T &scalar) { for (auto &x: coeff_) x /= scalar; return *this; } friend DenseFPS operator/(const DenseFPS &f, const T &scalar) { return DenseFPS(f) /= scalar; } friend DenseFPS operator/(const T &scalar, const DenseFPS &g) { return DenseFPS{scalar} /= g; } DenseFPS &operator/=(const DenseFPS &other) { return *this *= DenseFPS(Mult::invert(other.coeff_)); } friend DenseFPS operator/(const DenseFPS &f, const DenseFPS &g) { return f * DenseFPS(Mult::invert(g.coeff_)); } DenseFPS pow(Int t) const { assert(t >= 0); DenseFPS res = {1}, base = *this; while (t) { if (t & 1) res *= base; base *= base; t >>= 1; } return res; } // Multiplies by (1 + c * x^k). void multiply2_inplace(int k, int c) { assert(k > 0); if (size() <= dmax()) { coeff_.resize(min(size() + k, dmax() + 1), 0); } for (int i = size() - 1; i >= k; --i) { coeff_[i] += coeff_[i - k] * c; } } // Multiplies by (1 + c * x^k). DenseFPS multiply2(int k, int c) const { DenseFPS res = *this; res.multiply2_inplace(k, c); return res; } // Divides by (1 + c * x^k). void divide2_inplace(int k, int c) { assert(k > 0); for (int i = k; i < size(); ++i) { coeff_[i] -= coeff_[i - k] * c; } } // Divides by (1 + c * x^k). DenseFPS divide2(int k, int c) const { DenseFPS res = *this; res.divide2_inplace(k, c); return res; } // Multiplies by x^k. void shift_inplace(int k) { if (k > 0) { if (size() <= dmax()) { coeff_.resize(min(size() + k, dmax() + 1), 0); } for (int i = size() - 1; i >= k; --i) { coeff_[i] = coeff_[i - k]; } for (int i = k - 1; i >= 0; --i) { coeff_[i] = 0; } } else if (k < 0) { k *= -1; for (int i = k; i < size(); ++i) { coeff_[i - k] = coeff_[i]; } for (int i = size() - k; i < size(); ++i) { // If coefficients of degrees higher than dmax() were truncated // beforehand, you lose the information. Ensure dmax() is big enough. coeff_[i] = 0; } } } // Multiplies by x^k. DenseFPS shift(int k) const { DenseFPS res = *this; res.shift_inplace(k); return res; } T eval(const T &a) const { T res = 0, x = 1; for (auto c: coeff_) { res += c * x; x *= a; } return res; } }; // Formal Power Series (sparse format). template struct SparseFPS { int size_; std::vector degree_; std::vector coeff_; SparseFPS() : size_(0) {} explicit SparseFPS(std::vector> terms) : size_(terms.size()), degree_(size_), coeff_(size_) { // Sort by degree. std::sort(terms.begin(), terms.end(), [](const auto &x, const auto &y) { return x.first < y.first; }); for (int i = 0; i < size_; ++i) { auto[d, c] = terms[i]; assert(d >= 0); degree_[i] = d; coeff_[i] = c; } } SparseFPS(std::initializer_list> terms) : SparseFPS(std::vector>(terms.begin(), terms.end())) {} inline int size() const { return size_; } inline const T &coeff(int i) const { return coeff_[i]; } inline int degree(int i) const { return degree_[i]; } int max_degree() const { return (size_ == 0) ? 0 : degree_.back(); } void emplace_back(int d, T c) { assert(d >= 0); if (not degree_.empty()) { assert(d > degree_.back()); } degree_.push_back(std::move(d)); coeff_.push_back(std::move(c)); ++size_; } // Returns the coefficient of x^d. T operator[](int d) const { auto it = std::lower_bound(degree_.begin(), degree_.end(), d); if (it == degree_.end() or *it != d) return (T) (0); int j = std::distance(degree_.begin(), it); return coeff_[j]; } SparseFPS &operator+=(const T &scalar) { for (auto &x: coeff_) x += scalar; return *this; } friend SparseFPS operator+(const SparseFPS &f, const T &scalar) { SparseFPS res = f; res += scalar; return res; } SparseFPS &operator+=(const SparseFPS &other) { *this = this->add(other); return *this; } friend SparseFPS operator+(const SparseFPS &f, const SparseFPS &g) { return f.add(g); } SparseFPS &operator*=(const T &scalar) { for (auto &x: coeff_) x *= scalar; return *this; } friend SparseFPS operator*(const SparseFPS &f, const T &scalar) { SparseFPS res = f; res *= scalar; return res; } SparseFPS &operator-=(const SparseFPS &other) { *this = this->add(other * -1); return *this; } friend SparseFPS operator-(const SparseFPS &f, const SparseFPS &g) { return f.add(g * -1); } private: SparseFPS add(const SparseFPS &other) const { SparseFPS res; int j = 0; // two pointers (i, j) for (int i = 0; i < size(); ++i) { const int deg = this->degree(i); for (; j < other.size() and other.degree(j) < deg; ++j) { res.emplace_back(other.degree(j), other.coeff(j)); } T c = this->coeff(i); if (j < other.size() and other.degree(j) == deg) { c += other.coeff(j); ++j; } if (c != 0) { res.emplace_back(deg, c); } } for (; j < other.size(); ++j) { res.emplace_back(other.degree(j), other.coeff(j)); } return res; } }; // Polynomial addition (dense + sparse). template FPS &operator+=(FPS &f, const SparseFPS &g) { for (int i = 0; i < g.size(); ++i) { if (g.degree(i) > FPS::dmax()) break; // ignore f.coeff_[g.degree(i)] += g.coeff(i); } return f; } template FPS operator+(const FPS &f, const SparseFPS &g) { auto res = f; res += g; return res; } template FPS operator+(const SparseFPS &f, const FPS &g) { return g + f; // commutative } // Polynomial multiplication (dense * sparse). template FPS &operator*=(FPS &f, const SparseFPS &g) { if (g.size() == 0) { return f *= 0; } const int gd_max = g.degree(g.size() - 1); const int fd_max = f.size() - 1; const int n = std::min(fd_max + gd_max, FPS::dmax()) + 1; if (f.size() < n) f.coeff_.resize(n); T c0 = 0; int j0 = 0; if (g.degree(0) == 0) { c0 = g.coeff(0); j0 = 1; } for (int fd = n - 1; fd >= 0; --fd) { f.coeff_[fd] *= c0; for (int j = j0; j < g.size(); ++j) { int gd = g.degree(j); if (gd > fd) break; f.coeff_[fd] += f[fd - gd] * g.coeff(j); } } return f; } template FPS operator*(const FPS &f, const SparseFPS &g) { auto res = f; res *= g; return res; } template FPS operator*(const SparseFPS &f, const FPS &g) { return g * f; // commutative } // Polynomial division (dense / sparse). template FPS &operator/=(FPS &f, const SparseFPS &g) { assert(g.size() > 0 and g.degree(0) == 0 and g.coeff(0) != 0); const auto ic0 = T(1) / g.coeff(0); for (int fd = 0; fd < f.size(); ++fd) { for (int j = 1; j < g.size(); ++j) { int gd = g.degree(j); if (fd < gd) break; f.coeff_[fd] -= f.coeff_[fd - gd] * g.coeff(j); } f.coeff_[fd] *= ic0; } return f; } template FPS operator/(const FPS &f, const SparseFPS &g) { FPS res = f; res /= g; return res; } constexpr int DMAX = 300 * 60 + 5; using DF = DenseFPS>; using SF = SparseFPS; auto solve() -> Real { int n = in, L = in; L *= 60; DUMP(L); vector S(n); DF f = {1.0}; Int ssum = 0; REP(i, n) { int smin, ssec; scanf("%d:%d", &smin, &ssec); DUMP(i, smin, ssec); S[i] = 60 * smin + ssec; ssum += S[i]; f *= SF{{0, 0.5}, {S[i], 0.5}}; //DUMP(f.coeff_); } if (L >= ssum) { return n; } DUMP(S); Real ans = 0; REP(i, n) { DF g = {1.0}; REP(j, n) { if (j == i) continue; g *= SF{{0, 0.5}, {S[j], 0.5}}; } g.divide2_inplace(1, -1); ans += min(g[L - 1], 1); } return ans; } int main() { // ios_base::sync_with_stdio(false), cin.tie(nullptr); cout << std::fixed << std::setprecision(18); const int T = 1;//in; REP(t, T) { auto ans = solve(); print(ans); } }