#pragma GCC optimize("Ofast") #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; typedef long long int ll; typedef unsigned long long ull; mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count()); ll myRand(ll B) { return (ull)rng() % B; } // 参考: // https://awakia-n.hatenablog.com/entry/20100515/1273922367 // 今後参考にしたい: // https://drive.google.com/file/d/15_gwYirAxwjbTMEq5MXaPEZAlzkbZfia/view struct BigInt{ vector d; bool minus = false; BigInt& normalize(){ int i = (int)d.size() - 1; while(i>=0 and d[i] == 0)--i; d.resize(i+1); if((int)d.size() == 0) { d.emplace_back(0); minus = false; } return *this; } int size(){ return d.size(); } BigInt(ll _x = 0){ if(_x < 0){ minus = true; _x = -_x; } while(_x){ d.emplace_back(_x%10); _x /= 10; } if(d.size() == 0){ d.emplace_back(0); } } BigInt(string _x){ for(char &c:_x){ if(c == '-'){ minus = true; } else{ d.emplace_back(c-'0'); } } reverse(d.begin(), d.end()); normalize(); } BigInt& operator = (const BigInt& x); BigInt& operator = (const ll& x); BigInt& operator = (const string& x); const bool operator < (const BigInt& x) const; const bool operator > (const BigInt& x) const; const bool operator <= (const BigInt& x) const; const bool operator >= (const BigInt& x) const; const bool operator != (const BigInt& x) const; const bool operator == (const BigInt& x) const; BigInt operator -() const; BigInt& operator += (const BigInt& x); BigInt& operator -= (const BigInt& x); BigInt& operator *= (const BigInt& x); BigInt& operator /= (const BigInt& x); BigInt& operator %= (const BigInt& x); const BigInt operator + (const BigInt& x) const; const BigInt operator - (const BigInt& x) const; const BigInt operator * (const BigInt& x) const; const BigInt operator / (const BigInt& x) const; const BigInt operator % (const BigInt& x) const; friend pair divmod (const BigInt& lhs, const BigInt& rhs); friend istream& operator >> (istream& is, BigInt& x); friend ostream& operator << (ostream& os, const BigInt& x); friend const BigInt abs(BigInt x); }; BigInt& BigInt::operator = (const BigInt& x){ minus = x.minus; d = x.d; return *this; } BigInt& BigInt::operator = (const ll& x){ return *this = BigInt(x); } BigInt& BigInt::operator = (const string& x){ return *this = BigInt(x); } const bool BigInt::operator < (const BigInt& x) const{ if(minus != x.minus) return (minus ? true : false); if(d.size() != x.d.size()) return (d.size() < x.d.size()) ^ minus; for (int i = (int)d.size()-1; i >= 0; --i){ if(d[i] != x.d[i]) return (d[i] < x.d[i]) ^ minus; } return false; } const bool BigInt::operator > (const BigInt& x) const{return x<(*this);} const bool BigInt::operator <= (const BigInt& x) const{return !(x<(*this));} const bool BigInt::operator >= (const BigInt& x) const{return !(x>(*this));} const bool BigInt::operator != (const BigInt& x) const{return (*this)= 10){ tmp = 1; d[i] -= 10; } else tmp = 0; } if(tmp) d.emplace_back(1); return *this; } BigInt& BigInt::operator -= (const BigInt& x){ if(minus != x.minus) return *this += -x; vector dd(x.d); if(((*this)normalize(); } BigInt& BigInt::operator *= (const BigInt& x){ minus ^= x.minus; int N1 = (int)d.size(); int N2 = (int)x.d.size(); int N = N1 + N2; vector dd(N); for (int i = 0; i < N1; ++i) { for (int j = 0; j < N2; ++j) { dd[i+j] += d[i] * x.d[j]; } } for (int i = 0; i+1 < N; ++i) { dd[i+1] += dd[i] / 10; dd[i] %= 10; } swap(d,dd); return this->normalize(); } BigInt& BigInt::operator /= (const BigInt& x){ return *this = divmod(*this, x).first; } BigInt& BigInt::operator %= (const BigInt& x){ return *this = divmod(*this, x).second; } const BigInt BigInt::operator + (const BigInt& x) const{ BigInt res(*this); return res += x; } const BigInt BigInt::operator - (const BigInt& x) const{ BigInt res(*this); return res -= x; } const BigInt BigInt::operator * (const BigInt& x) const{ BigInt res(*this); return res *= x; } const BigInt BigInt::operator / (const BigInt& x) const{ BigInt res(*this); return res /= x; } const BigInt BigInt::operator % (const BigInt& x) const{ BigInt res(*this); return res %= x; } pair divmod (const BigInt& lhs, const BigInt& rhs){ if((int)rhs.d.size() == 1 and rhs.d[0] == 0){ cerr << "error: division by zero" << endl; exit(1); } if(lhs < rhs){ return make_pair(BigInt(0), lhs); } BigInt base,q,r; int N = (int)lhs.d.size() - (int)rhs.d.size() + 1; base.d.resize(N); base.d.back() = 1; q.d.resize(N); r = lhs; for (int i = N-1; i >= 0; --i) { int L = 0, R = 10; while(R-L > 1){ int mid = (L+R)/2; if(BigInt(mid)*rhs*base <= r){ L = mid; } else{ R = mid; } } q.d[i] = L; r -= BigInt(L)*rhs*base; base.d.pop_back(); if(base.d.size()) base.d.back() = 1; } return make_pair(q.normalize(), r.normalize()); } istream& operator >> (istream& is, BigInt& x){ string s; is >> s; x = BigInt(s); return is; } ostream& operator << (ostream& os, const BigInt& x){ if(x.minus) os << '-'; int N = x.d.size(); for (int i = N-1; i >= 0; --i){ os << x.d[i]; } return os; } const BigInt abs(BigInt x){ x.minus = false; return x; } int main(){ cin.tie(nullptr); ios::sync_with_stdio(false); BigInt res=BigInt(0); int n; cin >> n; for(int i=0;i> s; string t=""; bool flg = false; for(char c:s){ if(c=='.'){ flg = true; } else{ t+=c; if(flg)m--; } } BigInt a = BigInt(t); for(int j=0;j