#include using namespace std; #define REP(i,n) for(int i=0;i<(int)(n);++i) #define FOR(i,c) for(__typeof((c).begin())i=(c).begin();i!=(c).end();++i) #define ALL(c) (c).begin(), (c).end() #define valid(y,x,h,w) (0<=y&&y pii; templatebool chmax(T &a, const T &b) { if (abool chmin(T &a, const T &b) { if (bostream&operator<<(ostream &o,const vector&t){o<<'[';FOR(i,t){if(i!=t.begin())o<<',';o<<*i;}return o<<']';} templateostream&operator<<(ostream &o,const pair&t){return o<<'('<void output(ostream&,const Tp&){} templatevoid output(ostream &o,const Tp&t){if(N)o<<',';o<(t);output(o,t);} templateostream&operator<<(ostream&o,const tuple&t){o<<'(';output<0,tuple,Ts...>(o,t);return o<<')';} templatevoid output(T t,char z=10){if(t<0)t=-t,putchar(45);int c[20]; int k=0;while(t)c[k++]=t%10,t/=10;for(k||(c[k++]=0);k;)putchar(c[--k]^48);putchar(z);} templatevoid outputs(T t){output(t);} templatevoid outputs(S a,T...t){output(a,32);outputs(t...);} templatevoid output(T *a,int n){REP(i,n)output(a[i],i!=n-1?',':10);} templatevoid output(T *a,int n,int m){REP(i,n)output(a[i],m);} templatebool input(T &t){int n=1,c;for(t=0;!isdigit(c=getchar())&&~c&&c-45;); if(!~c)return 0;for(c-45&&(n=0,t=c^48);isdigit(c=getchar());)t=10*t+c-48;t=n?-t:t;return 1;} templatebool input(S&a,T&...t){input(a);return input(t...);} templatebool inputs(T *a, int n) { REP(i,n) if(!input(a[i])) return 0; return 1;} template T gcd(T a, T b) { if (a <= 0) return b; return gcd(b % a, a); } template struct Rational { T p, q; Rational(T p = 0, T q = 1) : p(p), q(q) { normalize(); } void normalize() { if (q < 0) { p=-p;q=-q; } T d = gcd(abs(p), q); if (d == 0) p = 0, q = 1; else p /= d, q /= d; } Rational inv() { return Rational(q, p); } Rational &operator-() { p *= -1; return *this; } Rational operator-() const { return Rational(-p, q); } Rational operator+(const Rational &rhs) const { return Rational(p * rhs.q + rhs.p * q, q * rhs.q); } Rational operator-(const Rational &rhs) const { return Rational(p * rhs.q - rhs.p * q, q * rhs.q); } Rational operator*(const Rational &rhs) const { return Rational(p * rhs.p, q * rhs.q); } Rational operator/(const Rational &rhs) const { return Rational(p * rhs.q, q * rhs.p);} Rational &operator+=(const Rational &rhs) { *this = *this + rhs; return *this; } Rational &operator-=(const Rational &rhs) { *this = *this - rhs; return *this; } Rational &operator*=(const Rational &rhs) { *this = *this * rhs; return *this; } Rational &operator/=(const Rational &rhs) { *this = *this / rhs; return *this; } bool operator<(const Rational &rhs) const { return p * rhs.q < rhs.p * q; } bool operator>(const Rational &rhs) const { return p * rhs.q > rhs.p * q; } bool operator<=(const Rational &rhs) const { return p * rhs.q <= rhs.p * q; } bool operator>=(const Rational &rhs) const { return p * rhs.q >= rhs.p * q; } bool operator!=(const Rational &rhs) const { return p * rhs.q != rhs.p * q; } bool operator==(const Rational &rhs) const { return p * rhs.q == rhs.p * q; } string to_f(int digit) const { stringstream ss; T t = p; REP(i,digit+1) { ss << t/q; if (!i) ss << '.'; t = t%q*10; } return ss.str(); } friend Rational gcd(const Rational &a, const Rational &b) { T lcm = a.q*b.q / gcd(a.q, b.q); T p1 = a.p * lcm / a.q; T p2 = b.p * lcm / b.q; return Rational(gcd(p1, p2), lcm); } friend Rational abs(const Rational &rhs) { return Rational(abs(rhs.p), rhs.q); } friend ostream &operator<<(ostream &os, const Rational &rhs) { os << '(' << rhs.p << "/" << rhs.q << ')'; return os; } }; struct Long { static const long long BASE = 10000; static const int BW = 4; vector digits; Long(long long a = 0) { digits.push_back(a); Normalize(); } Long(const string &str) { if (str.length() == 0) { digits.push_back(0); } else { int s = str[0] != '-' ? 1 : -1; int sw = s == -1 ? 1 : 0; digits = vector((str.size() - 1 - sw) / BW + 1); int i = (str.size() - sw) % BW; int index = digits.size() - 1; if (i > 0) { i -= BW; } for (; i < (int)str.size() - sw; i+= BW) { long long a = 0; for (int j = 0; j < BW; j++) { a = 10 * a + (i + j + sw >= sw ? str[i + j + sw] - '0' : 0); } digits[index--] = a * s; } } Normalize(); } void resize(int s) { digits.resize(s); } int size() const { return digits.size(); } // size of vector of digits int size2() const { // number of digits return abs().toString().size(); } int sign() const { return digits[digits.size() - 1] > 0 ? 1 : (digits[digits.size() - 1] < 0 ? -1 : 0); } string toString() const { int s = sign(); ostringstream os; os << digits[size() - 1]; for (int i = size() - 2; i >= 0; i--) os << setw(Long::BW) << setfill('0') << digits[i] * s; return os.str(); } Long abs() const { Long ret = *this; return ret.sign() >= 0 ? ret : -ret;; } long long operator[](int index) const { return digits[index]; } long long &operator[](int index) { return digits[index]; } bool operator<(const Long &rhs) const { const Long &lhs = *this; if (lhs.sign() != rhs.sign()) { return lhs.sign() < rhs.sign(); } if (lhs.size() != rhs.size()) { return lhs.sign() > 0 ? lhs.size() < rhs.size() : lhs.size() > rhs.size(); } for (int i = lhs.size() - 1; i >= 0; i--) { if (lhs[i] != rhs[i]) { return lhs[i] < rhs[i]; } } return false; } bool operator>(const Long &rhs) const { return rhs < *this; } bool operator<=(const Long &rhs) const { return !(rhs < *this); } bool operator>=(const Long &rhs) const { return !(*this < rhs); } bool operator!=(const Long &rhs) const { return *this < rhs || rhs < *this; } bool operator==(const Long &rhs) const { return !(*this < rhs) && !(rhs < *this); } Long &Normalize() { int s = 1; while (digits[size() - 1] <= -BASE) { ll v = digits[size() - 1] / BASE; digits.push_back(v); digits[size() - 2] -= v * BASE; } for (int i = 0; i < size(); i++) { if (i == size() - 1 && digits[i] < 0) { goto minus; } else if (digits[i] < 0) { long long a = -((digits[i] + 1) / BASE) + 1; digits[i] = a * BASE + digits[i]; digits[i + 1] -= a; } else if (digits[i] >= BASE) { if (i == size() - 1) { digits.push_back(0); } long long a = digits[i] / BASE; digits[i] = digits[i] % BASE; digits[i + 1] += a; } assert(0 <= digits[i] && digits[i] < BASE); if (digits[i] != 0) { s = i + 1; } } assert(0 <= digits[s - 1] && digits[s - 1] < BASE); assert(s == 1 || digits[s - 1] != 0); resize(s); return *this; minus: s = 1; for (int i = size() - 2; i >= 0; i--) { digits[i + 1] += 1; digits[i] -= BASE; if (digits[i + 1] != 0) { s = max(s, i + 2); } assert(digits[i + 1] <= 0); assert(digits[i] <= 0); } resize(s); return *this; } Long operator+(const Long &rhs) const { Long ret = *this; if (ret.size() < rhs.size()) { ret.resize(rhs.size()); } for (int i = 0; i < rhs.size(); i++) { ret[i] += rhs[i]; } return ret.Normalize(); } Long operator-(const Long &rhs) const { //assert(*this >= rhs); Long ret = *this; if (ret.size() < rhs.size()) { ret.resize(rhs.size()); } for (int i = 0; i < rhs.size(); i++) { ret[i] -= rhs[i]; } return ret.Normalize(); } Long operator*(const Long &rhs) const { const Long &lhs = *this; Long ret; ret.resize(this->size() + rhs.size()); for (int i = 0; i < lhs.size(); i++) { for (int j = 0; j < rhs.size(); j++) { ret[i + j] += lhs[i] * rhs[j]; } } return ret.Normalize(); } Long operator/(const Long &rhs) const { return this->divmod(rhs).first; } Long operator%(const Long &rhs) const { return this->divmod(rhs).second; } Long operator-() const { return *this * -1; } Long &operator+=(const Long &rhs) { return *this = *this + rhs; } Long &operator-=(const Long &rhs) { return *this = *this - rhs; } Long &operator*=(const Long &rhs) { return *this = *this * rhs; } Long &operator/=(const Long &rhs) { return *this = *this / rhs; } Long &operator/=(long long rhs) { return *this = *this / rhs; } Long &operator%=(const Long &rhs) { return *this = *this % rhs; } pair divmodll(long long rhs) const { Long ret = *this; long long c = 0; long long t; for (int i = ret.size() - 1; i >= 0; i--) { t = BASE * c + ret[i]; ret[i] = t / rhs; c = t % rhs; } return make_pair(ret.Normalize(), c); } pair divmod(Long rhs) const { Long lhs = *this; if (lhs.size() < rhs.size()) { return pair(0, lhs); } int s = lhs.sign() * rhs.sign(); lhs = lhs.abs(); rhs = rhs.abs(); long long F = BASE / (rhs[rhs.size() - 1] + 1); // multiplying good-factor lhs = lhs * F; rhs = rhs * F; Long ret; ret.resize(lhs.size() - rhs.size() + 1); for (int k = ret.size() - 1, i = lhs.size() - 1; k >= 0; k--, i--) { ret[k] = (i + 1 < lhs.size() ? lhs[i + 1] : 0) * BASE + (i < lhs.size() ? lhs[i] : 0); ret[k] /= rhs[rhs.size() - 1]; Long t; t.resize(k + rhs.size()); for (int m = 0; m < rhs.size(); m++) { t[k + m] = ret[k] * rhs[m]; } t.Normalize(); while (lhs < t) { ret[k] -= 1; for (int m = 0; m < rhs.size(); m++) { t[k + m] -= rhs[m]; } t.Normalize(); } lhs = lhs - t; } return make_pair(ret.Normalize() * s, lhs.divmodll(F).first * s); } Long pow(ll n) { Long A(*this); Long B(1); while(n) { if (n&1) B *= A; A *= A; n >>= 1; } return B; } }; ostream &operator<<(ostream &os, const Long &rhs) { os << rhs.toString(); return os; } istream &operator>>(istream &is, Long &rhs) { string s; is >> s; rhs = Long(s); return is; } Long abs(const Long &x) { return x<0?-x:x; } typedef Rational Rat; Rat a[101], b[101]; int main() { int n; while(input(n)) { a[0] = Long(4); a[1] = Long(3); for (int i=2; i<=n; ++i) a[i] = a[i-1]*Rat(19,4) - a[i-2]*Rat(3); cout << a[n].to_f(20) << endl; } }