#include typedef long long ll; typedef unsigned long long ull; #define FOR(i,a,b) for(int (i)=(a);i<(b);i++) #define REP(i,n) FOR(i,0,n) #define RANGE(vec) (vec).begin(),(vec).end() using namespace std; class CountExpectationProblem { public: // 残りの数値 k から終了までのサイコロをふる回数の期待値を Exp(k) とする。 // このとき // // * Exp(0) = 0 // * Exp(k) = Exp(K) (k < 0) (K を超えたら 0 にリセットされるので) // * Exp(k) = 1 + (Exp(k-1)+...+Exp(k-6))/6 (k>0) // // この連立方程式から Exp(K) を計算すれば良い // // Exp(K) = x として漸化式を計算する。 double F(int K, double x) { vector Exp(K+1,0); FOR(k,1,K+1) { Exp[k] = 1.0; for (int i = 1; i <= 6; ++i) Exp[k] += ((k-i>=0)? Exp[k-i] : x)/6.0; // k<0 のときは x (=~Exp(K)) を使う } return Exp[K]; } void solve_binserach(void) { int K; cin>>K; // // 漸化式より Exp(k) は初項 x = Exp(K) の関数 F(k,x) = Exp(k) とみなせる。 // y = F(x) = F(K,x) とすると F は明らかに x の単調増加関数 // よって二分探索で y=x との交点を計算できる。 double low = 0.0; double high = 10000; REP(i,100) { double mid = (low+high)*0.5; if (F(K, mid) > mid) low = mid; else high = mid; } cout<solve(); delete obj; return 0; } #endif