#line 1 "lib/template.hpp" #ifdef TEMPLATE #else #define TEMPLATE # pragma GCC optimize("O3") using namespace std; #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include using uint=unsigned; using ll=long long; using ull=unsigned long long; using ld=long double; using pii=pair; using pll=pair; using i128=__int128; templateusing vc=vector; templateusing vvc=vc>; templateusing vvvc=vvc>; templateusing smpq=priority_queue,greater>; templateusing bipq=priority_queue; #define rep(i,n) for(ll i=0;i<(ll)(n);i++) #define REP(i,j,n) for(ll i=(j);i<(ll)(n);i++) #define DREP(i,n,m) for(ll i=(n);i>=(m);i--) #define drep(i,n) for(ll i=((n)-1);i>=0;i--) #define rall(x) x.rbegin(),x.rend() #define mp make_pair #define pb push_back #define fi first #define se second #define is insert #define bg begin() #define ed end() #define all(x) x.begin(),x.end() void scan(int&a) { cin >> a; } void scan(ll&a) { cin >> a; } void scan(string&a) { cin >> a; } void scan(char&a) { cin >> a; } void scan(uint&a) { cin >> a; } void scan(ull&a) { cin >> a; } void scan(bool&a) { cin >> a; } void scan(ld&a){ cin>> a;} template void scan(vector&a) { for(auto&x:a) scan(x); } void read() {} template void read(Head&head, Tail&... tail) { scan(head); read(tail...); } #define INT(...) int __VA_ARGS__; read(__VA_ARGS__); #define LL(...) ll __VA_ARGS__; read(__VA_ARGS__); #define ULL(...) ull __VA_ARGS__; read(__VA_ARGS__); #define STR(...) string __VA_ARGS__; read(__VA_ARGS__); #define VC(type, name, ...) vector name(__VA_ARGS__); read(name); #define VVC(type, name, size, ...) vector> name(size, vector(__VA_ARGS__)); read(name); templatevoid print(T a) { cout << a; } template void print(vectora) { for(int i=0;i<(int)a.size();i++){if(i)cout<<" ";print(a[i]);}cout< void PRT(T a) { print(a); cout < void PRT(Head head, Tail ... tail) { print(head); cout << " "; PRT(tail...); return; } template bool chmin(T &x, F y){ if(x>y){ x=y; return true; } return false; } template bool chmax(T &x, F y){ if(x T floor(T a, T b) { return a / b - (a % b && (a ^ b) < 0); } template T ceil(T x, T y) { return floor(x + y - 1, y); } template T bmod(T x, T y) { return x - y * floor(x, y); } template pair divmod(T x, T y) { T q = floor(x, y); return {q, x - q * y}; } void YesNo(bool b){ cout<<(b?"Yes":"No")<stovi(const string&s,const string&S){ vcv(s.size()); rep(i,s.size()){ auto t=S.find(s[i]); assert(t!=string::npos); v[i]=t; } return v; } template T isqrt(T x){ T F=sqrtl(x); while((F+1)*(F+1)<=x)F++; while(F*F>x)F--; return F; } template vvctrans(const vvc&a){ assert(a.size()&&a[0].size()); vvcb(a[0].size(),vc(a.size())); rep(i,a.size())rep(j,a[0].size()){ b[j][i]=a[i][j]; } return b; } template vctrans(const vc&a){ assert(a.size()&&a[0].size()); vcb(a[0].size(),string(a.size(),0)); rep(i,a.size())rep(j,a[0].size()){ b[j][i]=a[i][j]; } return b; } template int popcount(T n){ return __builtin_popcountll(n); } template L sum(vc&a){ return accumulate(all(a),L(0)); } template vcsubset(T S){ vcans; for(T x=S;x>0;x=(x-1)&S)ans.pb(x); ans.pb(0); return ans; } template T max(vc&a){ return *max_element(all(a)); } template T min(vc&a){ return *min_element(all(a)); } #ifndef COMPRESSER_STRUCT #define COMPRESSER_STRUCT template struct Compresser{ vcx; Compresser(int n=0){x.reserve(n);} Compresser(const vc&xs){ x=xs; } void push(T p){built=false;x.pb(p);} bool built=false; void build(){ if(!chmax(built,1))return; sort(all(x)); x.erase(unique(all(x)),x.end()); } int find(T v){ build(); auto itr=lower_bound(all(x),v)-x.begin(); if(itr==x.size()||x[itr]!=v)return -1; return itr; } int find_next(T v){ build(); return lower_bound(all(x),v)-x.begin(); } int size(){ build(); return x.size(); } T operator[](int i)const{ assert(0<=i&&i vc presum(vc &a){ vc ret(a.size()+1); rep(i,a.size())ret[i+1]=ret[i]+a[i]; return ret; } template vc &operator+=(vc &a,F b){ for (auto&v:a)v += b; return a; } template vc &operator-=(vc&a,F b){ for (auto&v:a)v-=b; return a; } template vc &operator*=(vc&a,F b){ for (auto&v:a)v*=b; return a; } template constexpr T POW(T a,T b){ T res=1; while(b){ if(b&1)res*=a; a*=a; b/=2; } return res; } constexpr ll ten(ll a){ return POW(10,a); } templateconstexpr T inf=numeric_limits::max()/2-1; template int tbit(T x){ using U=make_unsigned_t; U y=(U)x; return y?(int)bit_width(y)-1:-1; } template int lbit(T x){ using U=make_unsigned_t; U y=(U)x; return y?(int)countr_zero(y):-1; } template int tbit(T x,int p){ using U=make_unsigned_t; constexpr int W=numeric_limits::digits; U y=(U)x; if(p<0)return -1; if(p>=W-1)return tbit(y); return tbit(y&((U(1)<<(p+1))-1)); } template int lbit(T x,int p){ using U=make_unsigned_t; constexpr int W=numeric_limits::digits; U y=(U)x; if(p<0)return lbit(y); if(p>=W)return -1; return lbit(y&(~U(0)<>(istream&is,i128&x){ string s;is>>s; x=0; int i=0,neg=0; if(s[0]=='-')neg=1,i=1; for(;i<(int)s.size();i++)x=x*10+s[i]-'0'; if(neg)x=-x; return is; } ostream& operator<<(ostream&os,i128 x){ if(x==0)return os<<0; if(x<0)os<<"-"; using u128=__uint128_t; u128 y=x<0?-(u128)x:(u128)x; string s; while(y)s.pb('0'+y%10),y/=10; reverse(all(s)); return os< ostream& operator<<(ostream&os,const pair&p){ return os<<"("< ostream& operator<<(ostream&os,const array&a){ os<<"["; rep(i,N){ if(i)os<<", "; os< ostream& operator<<(ostream&os,const vc&a){ os<<"["; rep(i,a.size()){ if(i)os<<", "; os< ostream& operator<<(ostream&os,const deque&a){ os<<"["; rep(i,a.size()){ if(i)os<<", "; os< ostream& operator<<(ostream&os,const set&s){ os<<"{"; bool f=0; for(auto&x:s){ if(f)os<<", "; f=1; os< ostream& operator<<(ostream&os,const multiset&s){ os<<"{"; bool f=0; for(auto&x:s){ if(f)os<<", "; f=1; os< ostream& operator<<(ostream&os,const unordered_set&s){ os<<"{"; bool f=0; for(auto&x:s){ if(f)os<<", "; f=1; os< ostream& operator<<(ostream&os,const map&m){ os<<"{"; bool f=0; for(auto&x:m){ if(f)os<<", "; f=1; os< ostream& operator<<(ostream&os,const unordered_map&m){ os<<"{"; bool f=0; for(auto&x:m){ if(f)os<<", "; f=1; os< ostream& operator<<(ostream&os,queueq){ vca; while(q.size())a.pb(q.front()),q.pop(); return os< ostream& operator<<(ostream&os,stacks){ vca; while(s.size())a.pb(s.top()),s.pop(); return os< ostream& operator<<(ostream&os,priority_queueq){ vca; while(q.size())a.pb(q.top()),q.pop(); return os< void debug_out(const T&x,const Ts&...xs){ cout<sync_with_stdio(0); #ifdef LOCAL cout<pw(n+1);pw[0]=1;rep(i,n)pw[i+1]=pw[i]*3; vcdpa(pw[n]); vcdpb(pw[n]); //0 -> まだ //1 -> Alice が取った //2 -> Bob が取った drep(bit,pw[n]){ ll done=1; rep(j,n){ int A=bit/pw[j]%3; done&=!!A; } if(done){ ll alice=0; rep(j,n){ if(bit/pw[j]%3==1){ alice+=a[j]; }else{ alice-=a[j]; } } if(alice>0)dpa[bit]=dpb[bit]=1; continue; } { ld l=0,r=1; rep(t,30){ ld m=(l+r)/2; auto vv=[&](ld tar){ ld tmp=0; rep(k,n){ if(bit/pw[k]%3==0){ ld tmp2=1e9; rep(l,n){ if(bit/pw[l]%3==0){ chmin(tmp2,dpa[bit+pw[l]*2]/a[l]+(a[l]-1)/a[l]*tar); } } chmax(tmp,dpb[bit+pw[k]]/a[k]+(a[k]-1)/a[k]*tmp2); } } return tmp; }; if(vv(m)-m>=0){ l=m; }else{ r=m; } } dpa[bit]=l; dpb[bit]=1; rep(k,n){ if(bit/pw[k]%3==0){ chmin(dpb[bit],dpa[bit+pw[k]*2]/a[k]+(a[k]-1)/a[k]*dpa[bit]); } } } } PRT(dpa[0]); } signed main(){ int t=1; // cin >> t; while(t--)solve(); }