#include #include #include #include #include #include #include #include #include #include #include namespace FastIn { static constexpr size_t BUF_SIZE=1<<17, INT_LEN=24, FLT_LEN=400; static char buf[BUF_SIZE|1]={}, *pos=buf, *endbuf=nullptr; FILE *fin; inline bool rebuffer() { // returns true <=> there is at least one unread character size_t rest=endbuf-pos; if (buf+rest > pos) { // buf[:pos] and buf[-pos:] are overlapping, which std::memcpy() // causes undefined behavior. return true; } std::memcpy(buf, pos, rest); pos = buf; size_t len=std::fread(pos+rest, 1, BUF_SIZE-rest, fin); *(endbuf = buf + (rest+len)) = 0; return *pos; } inline bool scan(char &in) { if ((in = *pos)) { ++pos; return true; } return rebuffer() && (in = *pos++); } inline bool scan(char *in) { if ((*in = *pos) == 0) { if (rebuffer() && (*in = *pos) == 0) { return false; } } ++in; while (true) { if ((*in = *pos++) == 0) { if (rebuffer() && (*in = *pos++) == 0) { return true; } } ++in; } } inline bool scan(double &in) { if (pos + FLT_LEN >= endbuf && !rebuffer()) { in = 0.0; return false; } #if 0 char *tmp; in = std::strtod(pos, &tmp); pos = ++tmp; return true; #else intmax_t intpart=0; bool is_neg=false; if (*pos == '-') { ++pos; is_neg = true; } while (*pos >= '0') { intpart = intpart*10 + *pos-'0'; ++pos; } if (*pos++ != '.') { in = (is_neg? -intpart:intpart); return true; } intmax_t fracpart=0; const char *startp=pos; while (*pos >= '0') { fracpart = fracpart*10 + *pos-'0'; ++pos; } constexpr double tenths[20]={ 1, 0.1, 0.01, 1e-3, 1e-4, 1e-5, 1e-6, 1e-7, 1e-8, 1e-9, 1e-10, 1e-11, 1e-12, 1e-13, 1e-14, 1e-15, 1e-16, 1e-17, 1e-18, 1e-19, }; in = intpart + fracpart*tenths[pos-startp]; if (is_neg) in = -in; ++pos; #endif return true; } template inline bool scan(Int &in) { in = 0; // assume that no redundant whitespace appears if (pos + INT_LEN >= endbuf && !rebuffer()) { return false; } if (std::is_signed::value) { if (*pos == '-') { in = ~*++pos+'1'; while (*++pos >= '0') { in = in*10 + ~*pos+'1'; } ++pos; return true; } } // assume that numbers are separated by the character whose value is // less than '0' (e.g. whitespaces, newlines) do { in = in*10 + *pos-'0'; } while (*++pos >= '0'); ++pos; return true; } inline bool eat() { if (*pos > ' ') { return true; } do { if (*pos == 0 && !rebuffer()) { return false; } } while (*++pos <= ' '); return true; } inline bool eat(char ch) { if (*pos == ch) { return true; } do { if (*pos == 0 && !rebuffer()) { return false; } } while (*++pos != ch); return true; } class Scanner { bool rebuffer() { return FastIn::rebuffer(); } public: Scanner(FILE *fin=stdin) { FastIn::fin = fin; endbuf = pos + std::fread(buf, 1, BUF_SIZE, fin); } template inline bool scan(T &in) { return FastIn::scan(in); } template inline bool scan(First &in, Rest &...ins) { return scan(in) && scan(ins...); } }; } FastIn::Scanner cin; int main() { int m; cin.scan(m); constexpr double e=exp(1); for (int i=0; i(b)/a)); } }