結果
| 問題 | No.428 小数から逃げる夢 |
| ユーザー |
 kei
|
| 提出日時 | 2018-12-13 01:35:09 |
| 言語 | C++14 (gcc 12.3.0 + boost 1.83.0) |
| 結果 |
TLE
|
| 実行時間 | - |
| コード長 | 20,630 bytes |
| コンパイル時間 | 3,158 ms |
| コンパイル使用メモリ | 201,384 KB |
| 実行使用メモリ | 12,356 KB |
| 最終ジャッジ日時 | 2023-10-25 08:51:17 |
| 合計ジャッジ時間 | 9,512 ms |
|
ジャッジサーバーID （参考情報） |
judge13 / judge14 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | TLE | - |
| testcase_01 | -- | - |
| testcase_02 | -- | - |
| testcase_03 | -- | - |
| testcase_04 | -- | - |
| testcase_05 | -- | - |
| testcase_06 | -- | - |
| testcase_07 | -- | - |
| testcase_08 | -- | - |
| testcase_09 | -- | - |
| testcase_10 | -- | - |
| testcase_11 | -- | - |
| testcase_12 | -- | - |
| testcase_13 | -- | - |
| testcase_14 | -- | - |
| testcase_15 | -- | - |
| testcase_16 | -- | - |
| testcase_17 | -- | - |
| testcase_18 | -- | - |
| testcase_19 | -- | - |
| testcase_20 | -- | - |
| testcase_21 | -- | - |
| testcase_22 | -- | - |
| testcase_23 | -- | - |
| testcase_24 | -- | - |
| testcase_25 | -- | - |
| testcase_26 | -- | - |
| testcase_27 | -- | - |
| testcase_28 | -- | - |
| testcase_29 | -- | - |
| testcase_30 | -- | - |
| testcase_31 | -- | - |
| testcase_32 | -- | - |
| testcase_33 | -- | - |
| testcase_34 | -- | - |
| testcase_35 | -- | - |
| testcase_36 | -- | - |
| testcase_37 | -- | - |
| testcase_38 | -- | - |
| testcase_39 | -- | - |
| testcase_40 | -- | - |
| testcase_41 | -- | - |
| testcase_42 | -- | - |
| testcase_43 | -- | - |
| testcase_44 | -- | - |
| testcase_45 | -- | - |
| testcase_46 | -- | - |
| testcase_47 | -- | - |
| testcase_48 | -- | - |
| testcase_49 | -- | - |
| testcase_50 | -- | - |
| testcase_51 | -- | - |
| testcase_52 | -- | - |
| testcase_53 | -- | - |
| testcase_54 | -- | - |
| testcase_55 | -- | - |
| testcase_56 | -- | - |
| testcase_57 | -- | - |
| testcase_58 | -- | - |
| testcase_59 | -- | - |
| testcase_60 | -- | - |
| testcase_61 | -- | - |
| testcase_62 | -- | - |
| testcase_63 | -- | - |
| testcase_64 | -- | - |
| testcase_65 | -- | - |
| testcase_66 | -- | - |
| testcase_67 | -- | - |
| testcase_68 | -- | - |
| testcase_69 | -- | - |
| testcase_70 | -- | - |
| testcase_71 | -- | - |
| testcase_72 | -- | - |
| testcase_73 | -- | - |
| testcase_74 | -- | - |
| testcase_75 | -- | - |
| testcase_76 | -- | - |
| testcase_77 | -- | - |
| testcase_78 | -- | - |
| testcase_79 | -- | - |
| testcase_80 | -- | - |
| testcase_81 | -- | - |
| testcase_82 | -- | - |
| testcase_83 | -- | - |
| testcase_84 | -- | - |
| testcase_85 | -- | - |
| testcase_86 | -- | - |
| testcase_87 | -- | - |
| testcase_88 | -- | - |
| testcase_89 | -- | - |
| testcase_90 | -- | - |
| testcase_91 | -- | - |
| testcase_92 | -- | - |
| testcase_93 | -- | - |
| testcase_94 | -- | - |
| testcase_95 | -- | - |
| testcase_96 | -- | - |
| testcase_97 | -- | - |
| testcase_98 | -- | - |
| testcase_99 | -- | - |
ソースコード
#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int INF = 1e9;
const ll LINF = 1e18;
inline ll gcd(ll a, ll b) { return b ? gcd(b, a%b) : a; }
inline ll lcm(ll a, ll b) { return a / gcd(a, b)*b; }
template<class S,class T> ostream& operator << (ostream& out,const pair<S,T>& o){ out << "(" << o.first << "," << o.second << ")"; return out; }
template<class T> ostream& operator << (ostream& out,const vector<T> V){ for(int i = 0; i < V.size(); i++){ out << V[i]; if(i!=V.size()-1) out << " ";} return out; }
template<class T> ostream& operator << (ostream& out,const vector<vector<T> > Mat){ for(int i = 0; i < Mat.size(); i++) { if(i != 0) out << endl; out << Mat[i];} return out; }
template<class S,class T> ostream& operator << (ostream& out,const map<S,T> mp){ out << "{ "; for(auto it = mp.begin(); it != mp.end(); it++){ out << it->first << ":" << it->second; if(mp.size()-1 != distance(mp.begin(),it)) out << ", "; } out << " }"; return out; }
/*
<url:https://yukicoder.me/problems/no/428>
問題文============================================================
=================================================================
解説=============================================================
================================================================
*/
namespace arithmetic {
template<typename T> class Addition {
public:
template<typename V> T operator+(const V& v) const {
return T(static_cast<const T&>(*this)) += v;
}
};
template<typename T> class Subtraction {
public:
template<typename V> T operator-(const V& v) const {
return T(static_cast<const T&>(*this)) -= v;
}
};
template<typename T> class Multiplication {
public:
template<typename V> T operator*(const V& v) const {
return T(static_cast<const T&>(*this)) *= v;
}
};
template<typename T> class Division {
public:
template<typename V> T operator/(const V& v) const {
return T(static_cast<const T&>(*this)) /= v;
}
};
template<typename T> class Modulus {
public:
template<typename V> T operator%(const V& v) const {
return T(static_cast<const T&>(*this)) %= v;
}
};
}
template<typename T> class IndivisibleArithmetic : public arithmetic::Addition<T>, public arithmetic::Subtraction<T>, public arithmetic::Multiplication<T> {};
template<typename T> class Arithmetic : public IndivisibleArithmetic<T>, public arithmetic::Division<T> {};
template<typename T> class Ordered {
public:
template<typename V> bool operator==(const V& v) const {
return !(static_cast<T>(v) < static_cast<const T&>(*this) || static_cast<const T&>(*this) < static_cast<T>(v));
}
template<typename V> bool operator!=(const V& v) const {
return static_cast<T>(v) < static_cast<const T&>(*this) || static_cast<const T&>(*this) < static_cast<T>(v);
}
template<typename V> bool operator>(const V& v) const {
return static_cast<T>(v) < static_cast<const T&>(*this);
}
template<typename V> bool operator<=(const V& v) const {
return !(static_cast<T>(v) < static_cast<const T&>(*this));
}
template<typename V> bool operator>=(const V& v) const {
return !(static_cast<const T&>(*this) < static_cast<T>(v));
}
};
const long double EPSILON = 1e-200;
template<int IntegerSize = 3, int DecimalSize = 200>
class BigDecimal : public Arithmetic<BigDecimal<IntegerSize, DecimalSize>>, public Ordered<BigDecimal<IntegerSize, DecimalSize>> {
private:
const static int BitSize = 31;
const static bool PLUS = false;
const static bool MINUS = true;
bool sign;
long long d[IntegerSize + DecimalSize];
public:
BigDecimal() {
*this = BigDecimal(0);
}
BigDecimal(int n) {
sign = PLUS;
for (auto& i : d) i = 0;
d[DecimalSize] = n;
normal();
}
BigDecimal(long long n) {
sign = PLUS;
for (auto& i : d) i = 0;
d[DecimalSize] = n;
normal();
}
BigDecimal(string str) {
*this = BigDecimal(0);
bool minus = false;
if (str[0] == '-') {
minus = true;
str = str.substr(1);
}
BigDecimal t = 1;
bool decimal = false;
for (int i = 0; i < (int)str.size(); ++i) {
if (str[i] == '.') {
decimal = true;
} else {
if (decimal) *this += (t /= 10) * (str[i] - '0');
else *this = *this * 10 + (str[i] - '0');
}
}
if (minus) sign = MINUS;
}
BigDecimal(double r) {
*this = BigDecimal(0);
int n;
BigDecimal b = (r >= 0 ? BigDecimal(1) : BigDecimal(-1));
r = 2 * abs(frexp(abs(r), &n));
b <<= n - 1;
while (r) {
if (r >= 1) {
*this += b;
r -= 1;
}
r *= 2;
b >>= 1;
}
}
BigDecimal(long double r) {
*this = BigDecimal(0);
int n;
BigDecimal b = (r >= 0 ? BigDecimal(1) : BigDecimal(-1));
r = 2 * abs(frexp(abs(r), &n));
b <<= n - 1;
while (r) {
if (r >= 1) {
*this += b;
r -= 1;
}
r *= 2;
b >>= 1;
}
}
BigDecimal normal() {
for (int i = 0; i < IntegerSize + DecimalSize - 1; ++i) {
d[i + 1] += d[i] >> BitSize;
d[i] &= (1ll << BitSize) - 1;
}
if (d[IntegerSize + DecimalSize - 1] < 0) {
sign = !sign;
for (int i = 0; i < IntegerSize + DecimalSize; ++i) d[i] = -d[i];
normal();
}
if (d[IntegerSize + DecimalSize - 1] >= (1ll << BitSize)) throw "overflow";
for (int i = 0; i < IntegerSize + DecimalSize; ++i) if (d[i] != 0) {
return *this;
}
sign = PLUS;
return *this;
}
BigDecimal operator-() const {
BigDecimal bd(*this);
bd.sign = !bd.sign;
return bd;
}
BigDecimal operator<<(int a) const {return BigDecimal(*this) <<= a;}
BigDecimal operator>>(int a) const {return BigDecimal(*this) >>= a;}
BigDecimal operator%(const BigDecimal &a) const {return BigDecimal(*this) %= a;}
BigDecimal operator<<=(int a) {
if (a < 0) return *this >>= -a;
while (a >= BitSize) {
if (d[IntegerSize + DecimalSize - 1]) throw "overflow";
for (int i = IntegerSize + DecimalSize; --i > 0; ) d[i] = d[i - 1];
d[0] = 0;
a -= BitSize;
}
if (d[IntegerSize + DecimalSize - 1] >= (1ll << (BitSize - a))) throw "overflow";
for (auto& i : d) i <<= a;
return normal();
}
BigDecimal operator>>=(int a) {
if (a < 0) return *this <<= -a;
while (a >= BitSize) {
for (int i = 0; i < IntegerSize + DecimalSize - 1; ++i) d[i] = d[i + 1];
d[IntegerSize + DecimalSize - 1] >>= BitSize;
a -= BitSize;
}
for (int i = 0; i < IntegerSize + DecimalSize - 1; ++i) {
d[i] |= d[i + 1] << BitSize;
d[i + 1] = 0;
}
for (auto& i : d) i >>= a;
return normal();
}
BigDecimal operator+=(const BigDecimal &a) {
if (sign == a.sign) for (int i = 0; i < IntegerSize + DecimalSize; ++i) d[i] += a.d[i];
else for (int i = 0; i < IntegerSize + DecimalSize; ++i) d[i] -= a.d[i];
return normal();
}
BigDecimal operator-=(const BigDecimal &a) {
return *this += -a;
}
BigDecimal operator*=(const BigDecimal& a) {
BigDecimal res = 0;
for (int i = 0; i < IntegerSize + DecimalSize; ++i) {
if (i < DecimalSize) res = (res + *this * a.d[i]) >> BitSize;
else res += *this * a.d[i] << (i - DecimalSize) * BitSize;
}
res.sign = (sign == a.sign ? PLUS : MINUS);
return *this = res.normal();
}
BigDecimal operator*=(const unsigned int& a) {
for (auto& i : d) i *= a;
return this->normal();
}
BigDecimal operator/=(const BigDecimal &a) {
if (a == 0) throw "divide by zero";
BigDecimal rev = (double)1 / a.toDouble();
for (int i = 0; i < 7; ++i) rev = (rev << 1) - a * rev * rev;
rev.sign = a.sign;
return *this *= rev;
}
BigDecimal operator%=(const BigDecimal &a) {
if (a == 0) throw "modulo by zero";
return *this -= floor(*this / a) * a;
}
BigDecimal operator-(const BigDecimal& v) const {
return BigDecimal(*this) -= v;
}
BigDecimal operator++() {
return *this += 1;
}
BigDecimal operator++(int) {
BigDecimal bd = *this;
*this += 1;
return bd;
}
BigDecimal operator--() {
return *this -= 1;
}
BigDecimal operator--(int) {
BigDecimal bd = *this;
*this -= 1;
return bd;
}
bool operator<(const BigDecimal &a) const {
BigDecimal aa = a - EPSILON;
if (sign == MINUS) {
if (aa.sign == MINUS) return -a < -*this;
else return true;
}
if (aa.sign == MINUS) return false;
for (int i = IntegerSize + DecimalSize; i-- > 0; ) if (d[i] != aa.d[i]) return d[i] < aa.d[i];
return false;
}
bool equals(const BigDecimal &a) const {
if (sign != a.sign) return false;
for (int i = 0; i < IntegerSize + DecimalSize; ++i) if (d[i] != a.d[i]) return false;
return true;
}
int toInt() const {
int res = 0;
for (int i = 0; i < IntegerSize; ++i) res += d[DecimalSize + i] << BitSize * i;
if (sign == MINUS) return -res;
return res;
}
long long toLongLong() const {
long long res = 0;
for (int i = 0; i < IntegerSize; ++i) res += d[DecimalSize + i] << BitSize * i;
if (sign == MINUS) return -res;
return res;
}
string toString(int digit = 100, string mode = "near") const {
string str;
BigDecimal a = *this, bd = 1;
if (a.sign == MINUS) {
str += "-";
a.sign = PLUS;
}
if (mode == "near") {
BigDecimal round = BigDecimal(0.5);
for (int i = 0; i < digit; ++i) round /= 10;
a += round + EPSILON;
}
if (mode == "ceil") {
BigDecimal round = 1;
for (int i = 0; i < digit; ++i) round /= 10;
a += round - EPSILON;
}
for (; bd <= a; bd *= 10) ++digit;
if (bd > 1) {
bd /= 10;
--digit;
}
for (int i = 0; i < digit + 1; ++i) {
if (bd == 0) {
str += "0";
continue;
}
if (bd * 10 == 1) str += ".";
int d = 0;
while (bd < a) {
a -= bd;
++d;
}
if (d > 9) {
d -= 10;
string::iterator itr = str.end();
while (true) {
if (itr == str.begin()) {
str = "1" + str;
break;
}
--itr;
if (*itr == '.') continue;
++*itr;
if (*itr > '9') *itr = '0';
else break;
}
}
str += '0' + d;
bd /= 10;
}
return str;
}
double toDouble() const {
double res = 0;
for (int i = 0; i < IntegerSize + DecimalSize; ++i) res += d[i] * pow(2, (i - DecimalSize) * BitSize);
if (sign == MINUS) return -res;
return res;
}
bool isPlus() const {
return sign == PLUS;
}
bool isMinus() const {
return sign == MINUS;
}
template<int I, int D>
friend BigDecimal<I, D> pow(const BigDecimal<I, D> &x, const BigDecimal<I, D> &y);
template<int I, int D>
friend BigDecimal<I, D> floor(BigDecimal<I, D> x);
};
template<int IntegerSize, int DecimalSize>
BigDecimal<IntegerSize, DecimalSize> pi() {
const static BigDecimal<IntegerSize, DecimalSize> PI = (atan(BigDecimal<IntegerSize, DecimalSize>(1) / 5) << 4) - (atan(BigDecimal<IntegerSize, DecimalSize>(1) / 239) << 2);
return PI;
}
template<int IntegerSize, int DecimalSize>
inline BigDecimal<IntegerSize, DecimalSize> operator+(const int& a, BigDecimal<IntegerSize, DecimalSize> b) {
return BigDecimal<IntegerSize, DecimalSize>(a) + b;
}
template<int IntegerSize, int DecimalSize>
inline BigDecimal<IntegerSize, DecimalSize> operator-(const int& a, BigDecimal<IntegerSize, DecimalSize> b) {
return BigDecimal<IntegerSize, DecimalSize>(a) - b;
}
template<int IntegerSize, int DecimalSize>
inline BigDecimal<IntegerSize, DecimalSize> operator*(const int& a, BigDecimal<IntegerSize, DecimalSize> b) {
return BigDecimal<IntegerSize, DecimalSize>(a) * b;
}
template<int IntegerSize, int DecimalSize>
inline BigDecimal<IntegerSize, DecimalSize> operator/(const int& a, BigDecimal<IntegerSize, DecimalSize> b) {
return BigDecimal<IntegerSize, DecimalSize>(a) / b;
}
template<int IntegerSize, int DecimalSize>
ostream &operator<<(ostream &os, BigDecimal<IntegerSize, DecimalSize> a) {
os << a.toString(os.precision());
return os;
}
template<int IntegerSize, int DecimalSize>
istream &operator>>(istream &is, BigDecimal<IntegerSize, DecimalSize> &a) {
string str;
is >> str;
a = BigDecimal<IntegerSize, DecimalSize>(str);
return is;
}
template<int IntegerSize, int DecimalSize>
BigDecimal<IntegerSize, DecimalSize> sin(BigDecimal<IntegerSize, DecimalSize> x) {
BigDecimal<IntegerSize, DecimalSize> res = 0, xx = - x * x;
for (int i = 1; ; i += 2) {
x /= max(i * (i - 1), 1);
if (x.equals(0)) break;
res += x;
x *= xx;
}
return res;
}
template<int IntegerSize, int DecimalSize>
BigDecimal<IntegerSize, DecimalSize> cos(BigDecimal<IntegerSize, DecimalSize> x) {
BigDecimal<IntegerSize, DecimalSize> res = 0, xx = - x * x;
x = 1;
for (int i = 0; ; i += 2) {
x /= max(i * (i - 1), 1);
if (x.equals(0)) break;
res += x;
x *= xx;
}
return res;
}
template<int IntegerSize, int DecimalSize>
BigDecimal<IntegerSize, DecimalSize> tan(const BigDecimal<IntegerSize, DecimalSize> &x) {
return sin(x) / cos(x);
}
template<int IntegerSize, int DecimalSize>
BigDecimal<IntegerSize, DecimalSize> asin(BigDecimal<IntegerSize, DecimalSize> x) {
if (abs(x) > 1) throw "out of domain";
if (x > 1 / sqrt(BigDecimal<IntegerSize, DecimalSize>(2))) return (pi<IntegerSize, DecimalSize>() >> 1) - asin(sqrt(1 - x * x));
if (x < -1 / sqrt(BigDecimal<IntegerSize, DecimalSize>(2))) return -(pi<IntegerSize, DecimalSize>() >> 1) + asin(sqrt(1 - x * x));
BigDecimal<IntegerSize, DecimalSize> res = 0, xx = x * x >> 2;
for (int i = 0; ; ++i) {
x *= max(i * 2 * (i * 2 - 1), 1);
x /= max(i * i, 1);
auto add = x / (i * 2 + 1);
if (add.equals(0)) break;
res += add;
x *= xx;
}
return res;
}
template<int IntegerSize, int DecimalSize>
BigDecimal<IntegerSize, DecimalSize> acos(const BigDecimal<IntegerSize, DecimalSize> &x) {
return (pi<IntegerSize, DecimalSize>() >> 1) - asin(x);
}
template<int IntegerSize, int DecimalSize>
BigDecimal<IntegerSize, DecimalSize> atan(BigDecimal<IntegerSize, DecimalSize> x) {
if (x.isMinus()) return -atan(-x);
if (abs(x) > sqrt(2) + 1) return (pi<IntegerSize, DecimalSize>() >> 1) - atan(1 / x);
if (abs(x) > sqrt(2) - 1) return (pi<IntegerSize, DecimalSize>() >> 2) + atan((x - 1) / (x + 1));
BigDecimal<IntegerSize, DecimalSize> res = 0, xx = - x * x;
for (int i = 1; ; i += 2) {
auto add = x / i;
if (add.equals(0)) break;
res += add;
x *= xx;
}
return res;
}
template<int IntegerSize, int DecimalSize>
BigDecimal<IntegerSize, DecimalSize> atan2(const BigDecimal<IntegerSize, DecimalSize> &y, const BigDecimal<IntegerSize, DecimalSize> &x) {
if (x == 0) {
if (y > 0) return pi<IntegerSize, DecimalSize>() / 2;
if (y < 0) return -pi<IntegerSize, DecimalSize>() / 2;
throw "origin can't define argument";
}
if (x.isPlus()) return atan(y / x);
if (y.isPlus()) return atan(y / x) + pi<IntegerSize, DecimalSize>();
return atan(y / x) - pi<IntegerSize, DecimalSize>();
}
template<int IntegerSize, int DecimalSize>
BigDecimal<IntegerSize, DecimalSize> sinh(BigDecimal<IntegerSize, DecimalSize> x) {
BigDecimal<IntegerSize, DecimalSize> res = 0, xx = x * x;
for (int i = 1; ; i += 2) {
x /= max(i * (i - 1), 1);
if (x.equals(0)) break;
res += x;
x *= xx;
}
return res;
}
template<int IntegerSize, int DecimalSize>
BigDecimal<IntegerSize, DecimalSize> cosh(BigDecimal<IntegerSize, DecimalSize> x) {
BigDecimal<IntegerSize, DecimalSize> res = 0, xx = x * x;
x = 1;
for (int i = 0; ; i += 2) {
x /= max(i * (i - 1), 1);
if (x.equals(0)) break;
res += x;
x *= xx;
}
return res;
}
template<int IntegerSize, int DecimalSize>
BigDecimal<IntegerSize, DecimalSize> tanh(const BigDecimal<IntegerSize, DecimalSize> &x) {return sinh(x) / cosh(x);}
template<int IntegerSize, int DecimalSize>
BigDecimal<IntegerSize, DecimalSize> exp(const BigDecimal<IntegerSize, DecimalSize> &x) {
BigDecimal<IntegerSize, DecimalSize> res = 0, xx = 1;
for (int i = 0; ; ++i) {
xx /= max(i, 1);
if (xx.equals(0)) break;
res += xx;
xx *= x;
}
return res;
}
template<int IntegerSize, int DecimalSize>
BigDecimal<IntegerSize, DecimalSize> log(const BigDecimal<IntegerSize, DecimalSize> &x) {
BigDecimal<IntegerSize, DecimalSize> y = log(x.toDouble());
BigDecimal<IntegerSize, DecimalSize> z = x / exp(y);
BigDecimal<IntegerSize, DecimalSize> a = (z - 1) / (z + 1);
BigDecimal<IntegerSize, DecimalSize> res = 0, b = a, aa = a * a;
for (int i = 1; ; i += 2) {
if (b.equals(0)) break;
res += b / i;
b *= aa;
}
return y + res * 2;
}
template<int IntegerSize, int DecimalSize>
BigDecimal<IntegerSize, DecimalSize> log10(const BigDecimal<IntegerSize, DecimalSize> &x) {
return log(x) / log(BigDecimal<IntegerSize, DecimalSize>(10));
}
template<int IntegerSize, int DecimalSize>
BigDecimal<IntegerSize, DecimalSize> pow(const BigDecimal<IntegerSize, DecimalSize> &x, const BigDecimal<IntegerSize, DecimalSize> &y) {
if (x.isMinus()) {
if (floor(y) == y) return floor(y).d[DecimalSize] % 2 ? -pow(-x, floor(y)) : pow(-x, floor(y));
throw "power of negative number";
}
return exp(y * log(x));
}
template<int IntegerSize, int DecimalSize>
BigDecimal<IntegerSize, DecimalSize> sqrt(const BigDecimal<IntegerSize, DecimalSize> &x) {
BigDecimal<IntegerSize, DecimalSize> r = 1 / sqrt(x.toDouble());
for (int i = 0; i < 7; ++i) r *= (3 - x * r * r) >> 1;
return BigDecimal<IntegerSize, DecimalSize>(1) / r;
}
template<int IntegerSize, int DecimalSize>
BigDecimal<IntegerSize, DecimalSize> abs(const BigDecimal<IntegerSize, DecimalSize> &x) {
return x.isPlus() ? x : -x;
}
template<int IntegerSize, int DecimalSize>
BigDecimal<IntegerSize, DecimalSize> ceil(const BigDecimal<IntegerSize, DecimalSize> &x) {
if (x.isMinus()) return -floor(-x);
auto f = floor(x);
return f == x ? f : x + 1;
}
template<int IntegerSize, int DecimalSize>
BigDecimal<IntegerSize, DecimalSize> floor(BigDecimal<IntegerSize, DecimalSize> x) {
if (x.isMinus()) return -ceil(-x);
x += EPSILON;
for (int i = 0; i < DecimalSize; ++i) x.d[i] = 0;
return x;
}
template<class T>
T solve(T res){
BigDecimal<3,200> bg("0.1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677787980818283848586878889909192939495969798991");
int N; cin >> N;
bg *= N;
res = bg.toString(200);
return res;
}
int main(void) {
cin.tie(0); ios_base::sync_with_stdio(false);
cout << solve<string>("") << endl;
return 0;
}