#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 constexpr size_t MAX_FIVE_IEXP=27; constexpr uint64_t FIVES[MAX_FIVE_IEXP+1]={ UINT64_C(0x0000000000000001), UINT64_C(0x0000000000000005), UINT64_C(0x0000000000000019), UINT64_C(0x000000000000007D), UINT64_C(0x0000000000000271), UINT64_C(0x0000000000000C35), UINT64_C(0x0000000000003D09), UINT64_C(0x000000000001312D), UINT64_C(0x000000000005F5E1), UINT64_C(0x00000000001DCD65), UINT64_C(0x00000000009502F9), UINT64_C(0x0000000002E90EDD), UINT64_C(0x000000000E8D4A51), UINT64_C(0x0000000048C27395), UINT64_C(0x000000016BCC41E9), UINT64_C(0x000000071AFD498D), UINT64_C(0x0000002386F26FC1), UINT64_C(0x000000B1A2BC2EC5), UINT64_C(0x000003782DACE9D9), UINT64_C(0x00001158E460913D), UINT64_C(0x000056BC75E2D631), UINT64_C(0x0001B1AE4D6E2EF5), UINT64_C(0x000878678326EAC9), UINT64_C(0x002A5A058FC295ED), UINT64_C(0x00D3C21BCECCEDA1), UINT64_C(0x0422CA8B0A00A425), UINT64_C(0x14ADF4B7320334B9), UINT64_C(0x6765C793FA10079D), }; constexpr size_t MAX_TEN_IEXP=19; constexpr uint64_t TENS[MAX_TEN_IEXP+1]={ UINT64_C(0x0000000000000001), UINT64_C(0x000000000000000A), UINT64_C(0x0000000000000064), UINT64_C(0x00000000000003E8), UINT64_C(0x0000000000002710), UINT64_C(0x00000000000186A0), UINT64_C(0x00000000000F4240), UINT64_C(0x0000000000989680), UINT64_C(0x0000000005F5E100), UINT64_C(0x000000003B9ACA00), UINT64_C(0x00000002540BE400), UINT64_C(0x000000174876E800), UINT64_C(0x000000E8D4A51000), UINT64_C(0x000009184E72A000), UINT64_C(0x00005AF3107A4000), UINT64_C(0x00038D7EA4C68000), UINT64_C(0x002386F26FC10000), UINT64_C(0x016345785D8A0000), UINT64_C(0x0DE0B6B3A7640000), UINT64_C(0x8AC7230489E80000), }; auto mp_muladd_1=[](uint64_t *mp, size_t &size, uint64_t mul, uint64_t cy) { mp += size; size_t i=-size; do { __uint128_t prod=__uint128_t(mp[i])*mul; mp[i] = prod+cy; cy = (mp[i]>64); } while (++i > 0); if (cy) { ++size; *mp = cy; } }; auto mp_geq=[](const uint64_t *lhs, size_t lsize, const uint64_t *rhs, size_t rsize) { if (lsize != rsize) return (lsize > rsize); size_t i=lsize-1; do { if (lhs[i] != rhs[i]) return (lhs[i] > rhs[i]); } while (i-- > 0); return true; }; auto mp_sub=[](uint64_t *lhs, size_t &lsize, const uint64_t *rhs, size_t rsize) { size_t i=-rsize; lhs += rsize; rhs += rsize; uint64_t cy=0; do { uint64_t tmp=rhs[i]+cy; cy = (lhs[i] < tmp); lhs[i] -= tmp; } while (++i > 0); if (cy) --*lhs; lhs += lsize-rsize; while (lsize > 1) { if (*--lhs) break; --lsize; } }; auto round_away=[](uint64_t is_neg, uint64_t last_bit, uint64_t half_bit, uint64_t more_bits) { return half_bit && (last_bit || more_bits); // switch (fegetround()) { // case FE_DOWNWARD: // return is_neg && (half_bit || more_bits); // case FE_TONEAREST: // return half_bit && (last_bit || more_bits); // case FE_TOWARDZERO: // return false; // case FE_UPWARD: // return !is_neg && (half_bit || more_bits); // default: // assert(0); // } }; union { uint64_t lu; double lf; } res; constexpr int SIGN_SH=63, EXP_SH=52; res.lu = 0; if (*pos == '-') { ++pos; res.lu = UINT64_C(1) << SIGN_SH; } while (*pos == '0') ++pos; uint64_t mantissa=0, exponent=0; uint64_t more_bits=0, last_bit=0, half_bit=0; if (*pos > '0') { uint64_t bigint[16+1]={}, bisize=1; uint64_t intpart=*pos-'0'; int count=1; ++pos; while (*pos >= '0') { intpart = intpart*10 + *pos-'0'; ++pos; if (++count == MAX_TEN_IEXP) break; } if (*pos < '0') { mantissa = intpart; int msb=63-__builtin_clzll(mantissa); exponent = msb; if (msb >= EXP_SH+1) { mantissa >>= (msb-(EXP_SH+1)); if (intpart & ((UINT64_C(1) << (msb-(EXP_SH+1)))-1)) more_bits = 1; if (*pos == '.') { while (*++pos == '0') /* nop */; if (*pos > '0') { more_bits = 1; while (*++pos >= '0') /* nop */; } } goto rounding; /* NOT REACHED */ } goto parsing_fraction; /* NOT REACHED */ } bigint[0] = intpart; intpart = *pos-'0'; count = 1; ++pos; while (*pos >= '0') { intpart = intpart*10 + *pos-'0'; ++pos; if (++count == MAX_TEN_IEXP) { mp_muladd_1(bigint, bisize, TENS[MAX_TEN_IEXP], intpart); intpart = 0; count = 0; if (bisize > 16) { exponent = 0x3FF; mantissa = 0; goto rounding; } } } if (count) mp_muladd_1(bigint, bisize, TENS[count], intpart); { mantissa = bigint[bisize-1]; int msb=63-__builtin_clzll(mantissa); exponent = (bisize-1) << 6 | msb; if (exponent > 0x3FF) { exponent = 0x3FF; mantissa = 0; goto rounding; } size_t ignored=bisize-1; if (bisize > 1) { if (msb > EXP_SH+1) { mantissa >>= (msb-(EXP_SH+1)); if (bigint[ignored] & ((UINT64_C(1) << (msb-(EXP_SH+1)))-1)) more_bits = 1; } else if (msb < EXP_SH+1) { mantissa <<= ((EXP_SH+1)-msb); mantissa |= bigint[bisize-2] >> (64-((EXP_SH+1)-msb)); if (bigint[--ignored] & ((UINT64_C(1) << (64-((EXP_SH+1)-msb)))-1)) more_bits = 1; } else { mantissa = bigint[bisize-1]; } if (more_bits == 0) for (size_t i=0; i>= (msb-(EXP_SH+1)); if (bigint[0] & ((UINT64_C(1) << (msb-(EXP_SH+1)))-1)) more_bits = 1; } if (*pos == '.') { while (*++pos == '0') /* nop */; if (*pos > '0') { more_bits = 1; while (*++pos >= '0') /* nop */; } } goto rounding; /* NOT REACHED */ } } parsing_fraction: { size_t lzero=0; int msb=(mantissa? 63-__builtin_clzll(mantissa):0); if (*pos != '.') { if (mantissa) { mantissa <<= ((EXP_SH+1)-msb); } goto rounding; } { const char *tmp=++pos; while (*pos == '0') ++pos; lzero = pos - tmp; if (*pos < '0') { mantissa <<= ((EXP_SH+1)-msb); goto rounding; } } if (mantissa == 0 && lzero+1 > 324) { if (*pos > '0') { more_bits = 1; while (*++pos >= '0') /* nop */; } goto rounding; } if (mantissa && msb+lzero >= EXP_SH+1) { if (*pos > '0') { more_bits = 1; while (*++pos >= '0') /* nop */; } mantissa <<= ((EXP_SH+1)-msb); goto rounding; } if (mantissa) mantissa <<= lzero; { uint64_t bigfrac[40+1]={}, bfsize=1; uint64_t bigfive[40+1]={1}, psize=1; if (mantissa == 0) exponent -= lzero; mp_muladd_1(bigfive, psize, FIVES[lzero%MAX_FIVE_IEXP], 0); for (size_t i=0; i= '0') { mp_muladd_1(bigfrac, bfsize, 10, *pos-'0'); mp_muladd_1(bigfive, psize, 5, 0); mantissa? (mantissa<<=1):(--exponent); if (mp_geq(bigfrac, bfsize, bigfive, psize)) { mp_sub(bigfrac, bfsize, bigfive, psize); mantissa |= 1; } ++pos; if (mantissa & (UINT64_C(1) << (EXP_SH+1))) { while (*pos == '0') ++pos; more_bits |= (*pos >= '0' || bfsize > 1 || bigfrac[0]); while (*pos >= '0') ++pos; goto rounding; } } while (bfsize > 1 || bigfrac[0]) { mp_muladd_1(bigfrac, bfsize, 2, 0); mantissa? (mantissa<<=1):(--exponent); if (mp_geq(bigfrac, bfsize, bigfive, psize)) { mp_sub(bigfrac, bfsize, bigfive, psize); mantissa |= 1; } if (mantissa & (UINT64_C(1) << (EXP_SH+1))) { more_bits |= (bfsize > 1 || bigfrac[0]); goto rounding; } } msb = 63 - __builtin_clzll(mantissa); mantissa <<= ((EXP_SH+1)-msb); } } rounding: if (exponent > UINT64_C(0x3FF) && exponent <= -UINT64_C(0x3FF)) { if (mantissa & ((UINT64_C(1) << -(exponent+0x3FF))-1)) more_bits |= 1; mantissa >>= -(exponent+0x3FE); exponent = -0x3FF; } half_bit = mantissa & 1; mantissa >>= 1; last_bit = mantissa & 1; if (round_away(res.lu>>SIGN_SH, last_bit, half_bit, more_bits)) { if (++mantissa & (UINT64_C(1) << (EXP_SH+1))) { ++exponent; mantissa >>= 1; } } if (mantissa & (UINT64_C(1) << EXP_SH)) { mantissa ^= UINT64_C(1) << EXP_SH; res.lu |= (exponent+0x3FF) << EXP_SH; } if (exponent+0x3FF < 0x800) res.lu |= mantissa; in = res.lf; ++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)); } }