QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#434042#8785. Fake Coin and Lying Scalesucup-team008#AC ✓145ms4188kbC++2313.8kb2024-06-08 14:22:532024-06-08 14:22:55

Judging History

你现在查看的是最新测评结果

  • [2024-06-08 14:22:55]
  • 评测
  • 测评结果:AC
  • 用时:145ms
  • 内存:4188kb
  • [2024-06-08 14:22:53]
  • 提交

answer

// {{{ y0105w49 template 24K21
// hi mom
#ifndef NULL
#ifdef __GNUC__
#ifndef __clang__
// #include <bits/stdc++.h>
#include <bits/extc++.h>
#include <tr2/dynamic_bitset>
#define EXTS
#else
#ifdef ARST
#include <bits/clang++.h>
#else
#ifndef _GLIBCXX_NO_ASSERT
#include <cassert>
#endif
#include <cctype>
#include <cerrno>
#include <cfloat>
#include <ciso646>
#include <climits>
#include <clocale>
#include <cmath>
#include <csetjmp>
#include <csignal>
#include <cstdarg>
#include <cstddef>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <cwchar>
#include <cwctype>
#if __cplusplus >= 201103L
#include <ccomplex>
#include <cfenv>
#include <cinttypes>
// #include <cstdalign>
#include <cstdbool>
#include <cstdint>
#include <ctgmath>
// #include <cuchar>
#endif
#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <exception>
#include <fstream>
#include <functional>
#include <iomanip>
#include <ios>
#include <iosfwd>
#include <iostream>
#include <istream>
#include <iterator>
#include <limits>
#include <list>
#include <locale>
#include <map>
#include <memory>
#include <new>
#include <numeric>
#include <ostream>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <stdexcept>
#include <streambuf>
#include <string>
#include <typeinfo>
#include <utility>
#include <valarray>
#include <vector>
#if __cplusplus >= 201103L
#include <array>
#include <atomic>
#include <chrono>
#include <codecvt>
#include <condition_variable>
#include <forward_list>
#include <future>
#include <initializer_list>
#include <mutex>
#include <random>
#include <ratio>
#include <regex>
#include <scoped_allocator>
#include <system_error>
#include <thread>
#include <tuple>
#include <typeindex>
#include <type_traits>
#include <unordered_map>
#include <unordered_set>
#endif
#if __cplusplus >= 201402L
#include <shared_mutex>
#endif
#if __cplusplus >= 201703L
#include <any>
#include <charconv>
// #include <execution>
#include <filesystem>
#include <optional>
// #include <memory_resource>
#include <string_view>
#include <variant>
#endif
#if __cplusplus >= 202002L
#include <barrier>
#include <bit>
#include <compare>
#include <concepts>
#if __cpp_impl_coroutine
# include <coroutine>
#endif
#include <latch>
#include <numbers>
#include <ranges>
#include <span>
// #include <stop_token>
#include <semaphore>
// #include <source_location>
// #include <syncstream>
#include <version>
#endif
#if __cplusplus > 202002L
// #include <expected>
// #include <spanstream>
#if __has_include(<stacktrace>)
# include <stacktrace>
#endif
#include <stdatomic.h>
#endif
#endif
#endif
#else
#error "unsupported"
#endif
#endif
using namespace std;
#ifdef ARST
#define JO 1
#define OJ 0
#else
#define JO 0
#define OJ 1
#endif
#define STR(x) #x
#define GCCDIAG(s) _Pragma(STR(GCC diagnostic s)) static_assert(true)
#define Wsave GCCDIAG(push)
#define Wpop GCCDIAG(pop)
#define Wsupp(w) GCCDIAG(ignored "-W" w)
#define Wpush(w) Wsave; Wsupp(w)
#define typeof __typeof__
namespace gbd_ns {
	template<typename C> struct is_iterable {
		template<class T> static long check(...);
		template<class T> static char check(int,typename T::const_iterator = C().end());
		enum {
			value = sizeof(check<C>(0)) == sizeof(char),
			neg_value = sizeof(check<C>(0)) != sizeof(char)
		};
	};
	template<class T> struct _gbd3C;
	template<class T> ostream &_gbd3(ostream &os,const T &x) { return _gbd3C<T>::call(os,x); }
	template<> ostream &_gbd3(ostream &os,const string &x) { return os<<'"'<<x<<'"'; }
	template<> ostream &_gbd3(ostream &os,char *const &x) { return os<<'"'<<x<<'"'; }
	template<class T> ostream &_gbd3_5(ostream &os,const T &x) { return _gbd3(os,x); }
	template<class A,class B> ostream &_gbd4(ostream &os,const pair<A,B> &p) {
		_gbd3(os<<'(',p.first);
		_gbd3(os<<',',p.second);
		return os<<')';
	}
	template<class T,size_t N> struct _gbd4_tupleC {
		static void call(ostream &os,const T &t) {
			_gbd4_tupleC<T,N-1>::call(os,t);
			os<<','<<get<N-1>(t);
		}
	};
	template<class T> struct _gbd4_tupleC<T,1> {
		static void call(ostream &os,const T &t) { os<<get<0>(t); }
	};
	template<typename... Types> ostream &_gbd4(ostream &os,const tuple<Types...> &t) {
		os<<'(';
		_gbd4_tupleC<tuple<Types...>,sizeof...(Types)>::call(os,t);
		return os<<')';
	}
	template<> ostream &_gbd4(ostream &os,const tuple<> &t) { (void)t; return os<<"()"; }
	template<class T> ostream &_gbd4(ostream &os,const T &x) {
		return os<<x;
	}
	template<class T> struct _gbd3C {
		template<class U=T> static ostream &call(ostream &os,enable_if_t<is_iterable<U>::value,const T> &V) {
			os<<"{";
			bool ff=0;
			for(const auto &E:V) _gbd3_5<decltype(E)>(ff?os<<",":os,E), ff=1;
			return os<<"}";
		}
		template<class U=T> static ostream &call(ostream &os,enable_if_t<is_iterable<U>::neg_value,const T> &x) {
			return _gbd4(os,x);
		}
	};
	template<class T,typename... Args> ostream &_gbd2(ostream &os,bool,vector<string>::iterator nm,const T &x,Args&&... args);
	ostream &_gbd2(ostream &os,bool,vector<string>::iterator) { return os; }
	template<typename... Args> ostream &_gbd2(ostream &os,bool fi,vector<string>::iterator nm,const char *x,Args&&... args) {
		return _gbd2(os<<(fi?"":"  ")<<x,0,nm+1,args...);
	}
	template<class T,typename... Args> ostream &_gbd2(ostream &os,bool fi,vector<string>::iterator nm,const T &x,Args&&... args) {
		return _gbd2(_gbd3<T>(os<<(fi?"":"  ")<<*nm<<"=",x),0,nm+1,args...);
	}
	vector<string> split(string s) {
		vector<string> Z;
		string z="";
		s+=',';
		int dep=0;
		for(char c:s) {
			if(c==',' && !dep) Z.push_back(z),z="";
			else z+=c;
			if(c=='(' || c=='{' || c=='[') ++dep;
			if(c==')' || c=='}' || c==']') --dep;
		}
		return Z;
	}
	template<typename... Args> ostream &_gbd1(ostream &os,const string &nm,Args&&... args) {
		return _gbd2(os,1,split(nm).begin(),args...);
	}
	template<typename... Args> string _gbd1(const string &nm,Args&&... args) {
		ostringstream oss;
		_gbd2(oss,1,split(nm).begin(),args...);
		return oss.str();
	}
}
bool DBG=1,EMACS=0;
#define dbg(...) (JO&&DBG?gbd_ns::_gbd1(cerr<<"\033[38;5;5m"<<__FILE__<<":"<<__LINE__<<(EMACS?":note: ":": "),#__VA_ARGS__,__VA_ARGS__)<<"\033[0m"<<endl:cerr)
#define dbgt(...) dbg(fmt_time(),__VA_ARGS__)
#define fmt(...) gbd_ns::_gbd1(#__VA_ARGS__,__VA_ARGS__)
template<class Fun> struct _y_combinator_result {
	Fun _fun;
	template<class T> explicit _y_combinator_result(T &&fun) : _fun(forward<T>(fun)) {}
	template<typename... Args> decltype(auto) operator()(Args&&... args) {
		return _fun(ref(*this),forward<Args>(args)...);
	}
};
template<class Fun> [[nodiscard]] decltype(auto) fix(Fun &&fun) {
	return _y_combinator_result<decay_t<Fun>>(forward<Fun>(fun));
}
#define nop void()
#define sz(x) (int((x).size()))
#define all(v) (v).begin(),(v).end()
#define forenum(i,...) for(int i:{-1}) for(__VA_ARGS__) if(++i,0) assert(0); else
#define forenumll(i,...) for(long long i:{-1}) for(__VA_ARGS__) if(++i,0) assert(0); else
#define forbs(k,i,bs) for(ptrdiff_t k=0,i=(bs)._Find_first();i<(ptrdiff_t)(bs).size();i=(bs)._Find_next(i),++k)
#define fordbs(k,i,bs) for(ptrdiff_t k=0,i=(bs).find_first();i<(ptrdiff_t)(bs).size();i=(bs).find_next(i),++k)
#define get(x,i) get<i>(x)
template<class T> T &smin(T &x,const T &y) { return y<x?x=y:x; }
template<class T> T &smax(T &x,const T &y) { return y>x?x=y:x; }
template<class T> bool inb(const T &x,const T &l,const T &r) { return l<=x&&x<=r; }
template<class T> bool cinb(const T &x,const T &l,const T &r) { return l<=r?l<=x&&x<=r:l<=x||x<=r; }
#define fi first
#define se second
#define pb push_back
#define eb emplace_back
template<template<class> class C,class T> T popv(C<T> &v) { T z=v.back(); v.pop_back(); return z; }
template<template<class> class C,class T> T popq(C<T> &v) { T z=v.front(); v.pop(); return z; }
template<template<class> class C,class T> T pops(C<T> &v) { T z=*v.begin(); v.erase(v.begin()); return z; }
template<template<class,class> class C,class K,class V> pair<K,V> popm(C<K,V> &v) { pair<K,V> z=*v.begin(); v.erase(v.begin()); return z; }
template<template<class> class C,class T> void erase1(C<T> &v,const T &x) { v.erase(v.find(x)); }
template<template<class> class C,class T> int lbi(C<T> &v,const T &x) { return int(lower_bound(all(v),x)-v.begin()); }
template<template<class> class C,class T> int findi(C<T> &v,const T &x) { auto it=lower_bound(all(v),x); return it!=v.end()&&*it==x?int(it-v.begin()):-1; }
template<class V> int sortu(V &v) { sort(all(v)); int z=int(unique(all(v))-v.begin()); v.resize(z); return z; }
template<typename T,typename... Args> T tee(T (*f)(Args... args),Args&&... args) { T z=f(forward<Args>(args)...); cout<<z<<endl; return z; }
template<typename... Args> void tee(void (*f)(Args... args),Args&&... args) { f(forward<Args>(args)...); }
#ifdef EXTS
template<class S,class T> using omap=__gnu_pbds::tree<S,T,less<S>,__gnu_pbds::rb_tree_tag,__gnu_pbds::tree_order_statistics_node_update>;
template<class T> using oset=omap<T,__gnu_pbds::null_type>;
template<class T> using rope=__gnu_cxx::rope<T>;
using dbitset=tr2::dynamic_bitset<>;
#endif
constexpr int e0=1, e1=10, e2=100, e3=1000;
constexpr int e4=10*e3, e5=100*e3, e6=1000*e3;
constexpr int e7=10*e6, e8=100*e6, e9=1000*e6;
constexpr long long e10=10LL*e9, e11=100LL*e9, e12=1000LL*e9;
constexpr long long e13=10*e12, e14=100*e12, e15=1000*e12;
constexpr long long e16=10*e15, e17=100*e15, e18=1000*e15;
constexpr __int128_t e21=__int128_t(e3)*e18, e24=__int128_t(e6)*e18, e27=__int128_t(e9)*e18;
constexpr __int128_t e30=e3*e27, e33=e6*e27, e36=e9*e27;
using ulll=__uint128_t;
using lll=__int128_t;
using ull=unsigned long long;
using ll=long long;
using uint=unsigned int;
using ushort=unsigned short;
using uchar=char;
using ld=long double;
#ifdef EXTS
using lld=__float128;
#endif
long long START_TIME=chrono::duration_cast<chrono::microseconds>(chrono::steady_clock::now().time_since_epoch()).count();
inline long long now_U_03BC_s() { return chrono::duration_cast<chrono::microseconds>(chrono::steady_clock::now().time_since_epoch()).count()-START_TIME; }
const char *fmt_time(long long U_03BC_s=now_U_03BC_s()) { static char dur[20]; sprintf(dur,"%llu.%03llus",U_03BC_s/e6,(U_03BC_s%e6)/e3); return dur; }
#define timed(cb) do { dbg("timed "#cb" ..."); unsigned long long start=now_U_03BC_s(); cb; dbg("timed "#cb" took",fmt_time(now_U_03BC_s()-start)); } while(0)
int arg1; bool inp; vector<string> args;
unsigned seed=unsigned(JO&&getenv("sd")?atoi(getenv("sd")):OJ?START_TIME:START_TIME%e5);
mt19937 igen(seed<<1),gen(seed<<1|1);
#define irand(...) (assert(!inp),_rand(igen,__VA_ARGS__))
#define rand(...) _rand(gen,__VA_ARGS__)
template<class T> enable_if_t<numeric_limits<T>::is_integer,T> _rand(mt19937 &g,T l,T r) { return uniform_int_distribution<T>(l,r)(g); }
template<class T> enable_if_t<numeric_limits<T>::is_integer,T> _rand(mt19937 &g,T n) { return _rand(g,T(1),n); }
[[deprecated]] int _rand(mt19937 &g) { return _rand(g,0,numeric_limits<int>::max()); }
template<class T> enable_if_t<numeric_limits<T>::is_iec559,T> _rand(mt19937 &g,T l,T r) { return uniform_real_distribution<T>(l,r)(g); }
bool _rand(mt19937 &g,double p) { return bernoulli_distribution(p)(g); }
template<class T> T _rand(mt19937 &g,initializer_list<T> il) { return *(il.begin()+_rand(g,0,(int)il.size()-1)); }
template<class T> T _rand(mt19937 &g,double p,T a,T b) { return _rand(g,p)?a:b; }
template<class T> T _rand(mt19937 &g,initializer_list<T> il,initializer_list<double> wt) { assert(il.size()==wt.size()); return *(il.begin()+discrete_distribution<int>(wt)(g)); }
#define random_shuffle(...) static_assert(false,"random_shuffle deprecated, use shuffle")
#define ine(x,e) (inp?cin>>(x),nop:((x)=(e),nop))
#define inr(x,...) ine(x,irand(__VA_ARGS__))
#define endl '\n'
string garb;
void exit0() { DBG=1; dbgt("gg (early)",seed); exit(0); }
#ifndef MAIN
#define MAIN _main
#endif
void MAIN();
int32_t main([[maybe_unused]]int argc,[[maybe_unused]]char *argv[]) {
	ios_base::sync_with_stdio(0); cin.tie(0); cin.exceptions(ios_base::failbit | ios_base::badbit);
	arg1=0,args={argv,argv+argc};
	if(sz(args)>1) {
		if(args[1][0]=='i') freopen((string(__FILE__).substr(0,string(__FILE__).find('.'))+"."+args[1].substr(1)+".in").c_str(),"r",stdin);
		else if(args[1][0]=='I') freopen(args[1].substr(1).c_str(),"r",stdin);
		else arg1=stoi(args[1]);
	}
	inp=!arg1;
	if(JO && getenv("EMACS")) EMACS=1;
	dbgt(arg1,seed,args);
	#ifdef QUIET
	DBG=0;
	#endif
	MAIN();
	DBG=1;
	dbgt("gg;wp",seed);
	return 0;
}
constexpr int inf=e9+99;
constexpr ll linf=1LL*e9*e9+99;
#if __cplusplus >= 202002L
constexpr long double U_03C4__ld=2*numbers::pi_v<long double>;
#else
const long double U_03C4__ld=2*acosl(-1);
#endif
#define U_03C4_ ((flt)U_03C4__ld)
constexpr long double U_03B5__ld=1e-8l;
#define U_03B5_ ((flt)U_03B5__ld)
// }}}
using flt=double; //CARE
constexpr int P=e9+7;//998'244'353;

#define ln log
const flt ln2=ln(2);
const flt ln3=ln(3);
const flt ln2pi=ln(U_03C4_);

flt F(int n) {
	if(n==0 || n==1) return 0;
	if(n==2) return ln2;
	if(n==3) return ln2+ln3;
	assert(n>=4);
	flt l=ln(n);
	return n*l-n+.5*(l+ln2pi);
}
flt f(int n,int k) {
	return ln2*k-ln3*n + F(n)-F(k)-F(n-k);
}


auto solve() { /* CURSOR START */
	int n,k; inr(n,e9), ine(k,arg1-1);
	dbg(n,k);

	// if(!k) return ln(3.*k+1)+ln3*n;
	if(k>n) return ln(3.*k+1);
	flt hi=f(n,k);
	flt nxt=k?f(n,k-1):hi;
	if(nxt>hi) return dbg(nxt,hi),ln(3.*k+1);

	int L=-1,R=k;
	for(;R-L>1;) {
		int M=midpoint(L,R);
		(f(n,M)<hi-5?L:R)=M;
	}
	return dbg(hi,L,R,k),ln(3.*k+1)-(hi+ln(k-R+1));
}



void _main() { int NTC=1;
	dbg(ln2,ln3,ln2pi);
	cout<<fixed<<setprecision(7);
	ine(NTC,5);
	for(int TC=1;TC<=NTC;TC++) {
		// cout<<"Case #"<<TC<<": ";
		tee(solve);
	}
	if(JO&&inp) assert((cin>>ws).eof());
}

这程序好像有点Bug,我给组数据试试?

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 4176kb

input:

2
100 0
100 1

output:

109.8612289
105.9491974

result:

ok q=0 (2 test cases)

Test #2:

score: 0
Accepted
time: 4ms
memory: 4092kb

input:

10000
32 6
45 98
67 57
35 70
29 3
22 81
59 12
48 16
63 69
99 36
60 36
32 47
73 91
81 30
7 7
71 57
38 60
35 19
92 40
3 17
21 71
54 62
95 67
60 50
10 20
19 80
64 73
10 21
70 97
84 3
26 22
38 47
37 38
31 91
11 37
73 17
75 98
8 74
73 60
87 10
94 48
35 73
18 14
88 25
61 54
39 59
100 90
70 98
73 21
92 11
...

output:

19.1110533
5.6869754
5.1474945
5.3518581
23.1858435
5.4971682
31.2614693
15.6983812
5.3375381
24.7063814
5.3294147
4.9558271
5.6131281
20.3146178
3.0910425
5.1474945
5.1984970
5.4186736
16.0262042
3.9512437
5.3659760
5.2311086
5.3082677
5.0172798
4.1108739
5.4847969
5.3936275
4.1588831
5.6767538
80....

result:

ok q=0 (10000 test cases)

Test #3:

score: 0
Accepted
time: 0ms
memory: 4172kb

input:

1
10000 0

output:

10986.1228867

result:

ok q=0 (1 test case)

Test #4:

score: 0
Accepted
time: 0ms
memory: 4188kb

input:

1
10000 10

output:

10905.6225818

result:

ok q=0 (1 test case)

Test #5:

score: 0
Accepted
time: 0ms
memory: 4112kb

input:

1
10000 100

output:

10365.7164338

result:

ok q=0 (1 test case)

Test #6:

score: 0
Accepted
time: 0ms
memory: 4104kb

input:

1
100000 0

output:

109861.2288668

result:

ok q=0 (1 test case)

Test #7:

score: 0
Accepted
time: 2ms
memory: 4120kb

input:

1000
867 38
906 28
876 34
182 38
692 59
986 55
675 20
699 12
741 82
154 11
264 6
682 4
176 19
728 69
37 95
501 56
998 96
495 52
359 86
750 19
726 39
794 6
268 16
609 70
414 45
182 19
123 68
909 56
880 71
419 8
679 14
363 16
751 35
299 73
852 35
901 36
903 63
425 85
416 33
80 89
863 91
491 32
603 84
...

output:

776.9263584
857.3392852
801.6236025
86.6269706
525.0748111
840.2369156
643.4395023
704.0093977
507.3228620
126.8486484
261.2929429
726.1118981
125.6570501
531.3941796
5.6559918
343.4407081
721.9947112
348.6315835
144.6054869
727.9407188
625.3916827
837.6055221
228.2039044
410.9294615
288.2933677
131...

result:

ok q=0 (1000 test cases)

Test #8:

score: 0
Accepted
time: 2ms
memory: 4180kb

input:

1000
71 766
31 464
8 194
12 296
69 506
55 518
31 237
73 576
50 685
1 137
29 661
58 508
46 870
33 172
66 94
41 634
38 725
94 163
94 45
34 685
71 486
95 511
37 108
54 643
64 94
1 624
48 283
1 64
23 122
3 866
52 798
68 669
43 460
68 187
50 403
31 877
100 191
44 512
33 50
91 732
37 584
22 501
46 93
81 7...

output:

7.7402295
7.2392150
6.3681872
6.7900972
7.3258075
7.3492308
6.5680779
7.4552985
7.6285176
6.0210233
7.5928703
7.3297497
7.8674886
6.2480429
5.6454469
7.5511869
7.6852436
6.1944054
12.6246571
7.6285176
7.2855065
7.3356340
5.7838252
7.5652753
5.6454469
7.5352967
6.7452363
5.2626902
5.9053618
7.8628820...

result:

ok q=0 (1000 test cases)

Test #9:

score: 0
Accepted
time: 91ms
memory: 4060kb

input:

100000
448906 73251
858780 829062
380117 529011
219451 974416
390411 446812
457769 678634
440286 29979
663948 267273
623318 824172
557346 329036
2366 757990
279231 95725
394222 75586
671713 417299
997686 156089
462641 704003
267172 15563
115033 76151
271539 36507
909436 341831
97232 987703
780566 75...

output:

242699.1735212
14.7266629
14.2773774
14.8882062
14.1085062
14.5264500
353454.7262833
96658.2688431
14.7207472
7083.8611350
14.6370382
60919.0164381
188055.0821241
3071.6471930
555162.1568808
14.5631507
223400.5601837
18.6689745
165838.4741846
160144.8754609
14.9017500
14.6385964
183509.9842102
84475...

result:

ok q=0 (100000 test cases)

Test #10:

score: 0
Accepted
time: 109ms
memory: 4120kb

input:

100000
740599 913
947030 8115
575926 9039
721122 7094
794424 8453
157723 6263
973352 1890
462079 302
333631 3870
435636 4238
572643 7448
775859 6119
343386 2778
486927 1883
880553 7918
878758 5150
274829 778
759586 5734
461205 6806
744940 1346
378522 4830
214767 1511
367452 9987
288068 9685
761467 1...

output:

805982.4133323
988105.0014141
579949.4119434
747487.2869297
820109.7136442
142607.1189376
1054350.1102927
504930.4345964
342767.8300107
451821.2786040
584224.5316517
812415.4508359
359187.7215032
521312.2301342
916726.2364602
930256.0937721
296061.6877089
796800.3109801
466532.5881672
807633.7431584...

result:

ok q=0 (100000 test cases)

Test #11:

score: 0
Accepted
time: 80ms
memory: 4164kb

input:

100000
3460 249080
4870 627106
7714 639325
6245 973410
5156 799724
2143 932101
3190 88015
5691 880401
4405 773261
157 516968
1022 535321
7679 193074
2293 754309
6302 607322
9422 65236
7327 352879
2188 417324
3181 532778
8804 165866
2433 321295
4829 557456
7228 613548
470 947610
2867 326654
1091 7711...

output:

13.5241430
14.4474837
14.4667810
14.8871733
14.6906347
14.8438091
12.4838786
14.7867454
14.6569846
14.2543492
14.2892348
13.2694428
14.6321701
14.4154272
12.1843841
13.8724937
14.0402313
14.2844730
13.1175498
13.7787283
14.3297517
14.4256266
14.8603109
13.7952701
14.6542094
13.3122727
14.1751774
14....

result:

ok q=0 (100000 test cases)

Test #12:

score: 0
Accepted
time: 108ms
memory: 4108kb

input:

100000
485911443 648621499
967545108 273118575
544774196 541753568
572826636 56596285
997351031 75012282
841305005 238445153
871651103 680174033
831928615 349267999
895576242 735170120
38669405 423897783
879163052 156607422
474161410 146955978
703868457 884260985
882781563 482183053
774752914 414027...

output:

21.3889722
297865546.3460265
21.2089341
405381381.5508109
777499095.0914496
257440439.5317873
21.4364715
105964408.9099599
21.5142248
20.9636152
445375780.6140419
125531071.7615605
21.6988751
27488635.7497014
28988566.0108602
21.1228010
20.9327565
21.2007988
1733351.9929168
21.8164155
380873.1253739...

result:

ok q=0 (100000 test cases)

Test #13:

score: 0
Accepted
time: 145ms
memory: 4092kb

input:

100000
998709247 6662353
938409567 5496364
470262254 388552
44631553 8053900
263812189 8140673
570847244 3686835
143527865 6364614
630983298 5151426
508843717 9845212
529080317 4866307
229185417 7424168
870671276 2477533
922155225 4868463
286532330 7131107
5469824 6272182
112064124 9288326
871839242...

output:

1052557876.3344299
993406423.1046485
513220014.7735955
22380605.5610956
247854665.6888012
602319074.5355741
127217813.6809350
659736907.6092513
503607562.8107697
550220073.1782553
213873956.9001667
937815586.2116394
979331032.1014258
276465510.8389332
16.7502472
84653733.6859751
918166748.7395298
29...

result:

ok q=0 (100000 test cases)

Test #14:

score: 0
Accepted
time: 48ms
memory: 4056kb

input:

100000
2388237 863104141
1949853 594471487
5788570 323905636
6626472 532884672
6478027 985480511
8713369 400770447
7877963 563355387
8572690 802705946
246447 691673591
1048191 39348128
9822372 87353076
4622806 985586908
3940664 689517333
7206000 907183324
7647553 126209541
9304319 816108273
3026286 ...

output:

21.6746582
21.3017956
20.6945751
21.1924279
21.8072522
20.9075117
21.2480335
21.6021113
21.4532370
18.5865713
19.3840811
21.8073602
21.4501147
21.7244674
19.7520664
21.6186699
21.2367299
20.8567949
21.4600165
21.2233529
20.9539225
21.3178649
21.1057381
20.8487911
21.7423433
21.7857226
21.5514018
21....

result:

ok q=0 (100000 test cases)

Test #15:

score: 0
Accepted
time: 68ms
memory: 4168kb

input:

100000
3230 990083111
447677 391972657
692146 408354973
191509 902573102
662501 450354073
721550 41375394
457751 109724688
636199 701346721
4329 135209393
7190 728002830
562092 480808431
608393 78791345
751611 613615532
576135 459945713
830181 180428675
549685 436319534
608642 828570290
40757 416064...

output:

21.8119117
20.8853149
20.9262597
21.7193725
21.0241569
18.6368092
19.6120972
21.4671252
19.8209475
21.5044278
21.0895918
19.2809260
21.3334914
21.0452313
20.1094584
20.9924977
21.6338245
20.9449642
20.8324905
20.8845389
21.5258311
18.9520540
21.2706877
21.4418865
21.3869018
21.6353946
21.4952195
20....

result:

ok q=0 (100000 test cases)

Test #16:

score: 0
Accepted
time: 56ms
memory: 4132kb

input:

100000
25834 61214455
26648 808954129
93315 645258548
40846 889138139
50931 688595112
83574 231579050
4476 298005500
10230 178645104
67274 582026639
45478 228216795
31799 640547396
76931 331956048
42831 764190687
32200 938076217
11303 774768820
48548 908303551
52646 376587760
30951 91507236
32097 76...

output:

19.0285062
21.6098651
21.3837739
21.7043755
21.4487763
20.3590441
20.6112348
20.0995240
21.2806391
20.3444189
21.3764460
20.7191254
21.5529402
21.7579540
21.5666875
21.7257015
20.8452740
19.4305409
21.5479008
21.4986984
20.8226416
20.1812511
21.6388362
19.1247767
21.2444758
21.5831750
21.6228915
20....

result:

ok q=0 (100000 test cases)

Test #17:

score: 0
Accepted
time: 132ms
memory: 4060kb

input:

100000
274227737 68346059
218685007 54356465
989024364 38654736
621112634 30460344
744276614 23921662
244777456 92571767
802238000 396401
867445410 73326922
915786289 8870270
283682509 84172313
874633287 75201041
511367562 84949073
634359016 56041772
732833967 55417420
693037815 93779223
439536157 2...

output:

99920320.2149020
79945806.4980072
896551039.6554644
539707002.9225786
695323400.1231637
42420665.7322038
877659783.8246883
650860090.1774502
949986390.1405026
80819165.7526486
652369973.1136773
272959464.6041659
468593091.6772850
570331669.4144413
421678375.9009724
381041977.2957881
166466182.122310...

result:

ok q=0 (100000 test cases)

Test #18:

score: 0
Accepted
time: 128ms
memory: 4176kb

input:

100000
145675394 9644
868401983 5079
81959359 7252
221259510 4525
210940342 503
709938567 8322
313226886 2026
284975389 1034
961263243 1271
708878403 8424
147154537 1117
597142707 9049
49009960 8469
632841549 912
998250617 5932
107131683 9999
243110679 3650
921083825 3103
645636937 7805
803218474 41...

output:

159931663.1069671
953967306.9924008
89961615.1861626
243021911.2999328
231734299.5063607
779838670.8942482
344087281.3261847
313062773.4088037
1056036267.6450124
778672746.1148727
161650736.1284156
655912591.3817157
53755251.3252818
695233704.1203023
1096608984.2068176
117586485.9601912
267037674.92...

result:

ok q=0 (100000 test cases)

Test #19:

score: 0
Accepted
time: 140ms
memory: 4108kb

input:

100000
415903859 143863
726725861 220923
721402153 142794
636365369 56467
195687608 492519
244711303 612418
892437244 320712
965738323 66085
653139241 592706
2885567 920921
430945805 947767
493265196 74615
877041778 105313
477250612 324587
932782139 573227
651591411 492931
438774413 597150
816745072...

output:

455527059.5820209
796226817.5022877
791081850.2214770
698496398.5906547
211203946.6896912
264138079.1507657
977355968.4372629
1060226382.8335525
712391733.9296752
724792.2231878
466038731.3723670
541124548.2992910
962399890.5278667
521396653.0085791
1019556750.6983215
711469336.3918132
477091393.100...

result:

ok q=0 (100000 test cases)

Test #20:

score: 0
Accepted
time: 124ms
memory: 4180kb

input:

100000
932735028 38475
303723723 37217
293643065 82693
53306635 90174
883367937 63149
414476477 62827
308746443 66010
319864936 52981
95584375 56035
201651629 95614
453621071 58910
638222297 35431
980668234 47930
725614760 41170
688105374 50896
958291243 76312
808245100 31656
617265859 68228
8643946...

output:

1024260600.1298995
333276403.1310682
321783884.8593203
57835244.6417936
969769150.9485332
454690074.0638615
338523081.9526152
350856629.7037233
104498327.7244210
220643283.5490197
497726776.0370626
700751703.9785376
1076817274.7288496
796697082.6762186
755390747.1917222
1051941111.6366886
887573183....

result:

ok q=0 (100000 test cases)

Test #21:

score: 0
Accepted
time: 0ms
memory: 4004kb

input:

1
1000 1000000000

output:

21.8218781

result:

ok q=0 (1 test case)

Test #22:

score: 0
Accepted
time: 0ms
memory: 3972kb

input:

1
1 100000000

output:

19.5192930

result:

ok q=0 (1 test case)

Test #23:

score: 0
Accepted
time: 0ms
memory: 3976kb

input:

1
100 1000000000

output:

21.8218781

result:

ok q=0 (1 test case)

Test #24:

score: 0
Accepted
time: 0ms
memory: 3976kb

input:

1
1 1000000000

output:

21.8218781

result:

ok q=0 (1 test case)

Test #25:

score: 0
Accepted
time: 0ms
memory: 4172kb

input:

1
1000000000 1000000000

output:

21.8218781

result:

ok q=0 (1 test case)

Extra Test:

score: 0
Extra Test Passed