I am sure my solution is right. But I even can not pass the example.
Hope you can help me.
dp[i][0..1] means the expected time for the last i digits while the i th digit carried or not carried.
f[i] means the possibility for the i th digit to carried.
p[0..1][x][y] means the possibility for x, y have appeared in the last i digits while the i th digit carried or not carried.

I know my code is boring and long.
my code is here.
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <deque>
#include <vector>
#include <queue>
#include <iostream>
#include <algorithm>
#include <map>
#include <set>
#include <ctime>
#include <iomanip>
using namespace std;
typedef long long LL;
typedef double DB;
#define MIT (2147483647)
#define INF (1000000001)
#define MLL (1000000000000000001LL)
#define sz(x) ((int) (x).size())
#define clr(x, y) memset(x, y, sizeof(x))
#define puf push_front
#define pub push_back
#define pof pop_front
#define pob pop_back
#define mk make_pair

const int N = 5010, M = 10;
int n;
DB cost[M][M], p[2][M][M], tmp[2][M][M], dp[N][2], f[N];

inline void input()
{
    scanf("%d", &n);
}

inline DB Cost(int x, int y, int t)
{
    DB ptxy = p[t][x][y] + p[t][y][x];
    return 1.0 * ptxy + cost[x][y] * (1 - ptxy);
}

inline void solve()
{
    for(int i = 0; i < 10; i++)
        for(int j = 0; j < 10; j++)
            if(i < 2 || j < 2) cost[i][j] = 1;
            else cost[i][j] = 2;
    int cnt = 0, cnt9 = 0;
    for(int x = 0; x < 10; x++)
        for(int y = 0; y < 10; y++)
        {
            if(x + y >= 10) cnt++;
            if(x + y == 9) cnt9++;
        }
    DB pJin = cnt / 100.0, p9 = cnt9 / 100.0;
    for(int i = 1; i < n; i++)
        f[i] = f[i - 1] * p9 + pJin;
    f[n] = f[n - 1] * (8 / 81.0) + (45.0 / 81.0);

    int cnt00, cnt01, cnt10, cnt11;
    DB tmp00, tmp01, tmp10, tmp11;
    for(int i = 1; i < n; i++)
    {
        cnt00 = cnt01 = cnt10 = cnt11 = 0, tmp00 = tmp01 = tmp10 = tmp11 = 0;
        for(int x = 0; x < 10; x++)
            for(int y = 0; y < 10; y++)
            {
                if(x + y <= 8)
                {
                    cnt00++, cnt10++;
                    tmp00 += Cost(x, y, 0), tmp10 += Cost(x, y, 1);
                }
                else if(x + y == 9)
                {
                    cnt00++, cnt11++;
                    tmp00 += Cost(x, y, 0), tmp11 += Cost(x, y, 1);
                }
                else if(x + y >= 10)
                {
                    cnt01++, cnt11++;
                    tmp01 += Cost(x, y, 0), tmp11 += Cost(x, y, 1);
                }
            }
        dp[i][0] += f[i - 1] * (dp[i - 1][1] + tmp10 / cnt10 + 1) +
                (1 - f[i - 1]) * (dp[i - 1][0] + tmp00 / cnt00);
        dp[i][1] += f[i - 1] * (dp[i - 1][1] + tmp11 / cnt11 + 1) +
                    (1 - f[i - 1]) * (dp[i - 1][0] + tmp01 / cnt01);
        dp[i][1] += 1; // write & mark

        for(int x = 0; x < 10; x++)
            for(int y = 0; y < 10; y++)
            {
                if(x + y <= 8)
                {
                    tmp[0][x][y] = (1 - f[i - 1]) * (p[0][x][y] + (1 - p[0][x][y]) / cnt00) +
                                   f[i - 1] * (p[1][x][y] + (1 - p[1][x][y]) / cnt10);
                    tmp[1][x][y] = (1 - f[i - 1]) * p[0][x][y] +
                                   f[i - 1] * p[1][x][y];
                }
                else if(x + y == 9)
                {
                    tmp[0][x][y] = (1 - f[i - 1]) * (p[0][x][y] + (1 - p[0][x][y]) / cnt00) +
                                   f[i - 1] * p[1][x][y];
                    tmp[1][x][y] = (1 - f[i - 1]) * p[0][x][y] +
                                   f[i - 1] * (p[1][x][y] + (1 - p[1][x][y]) / cnt11);
                }
                else if(x + y >= 10)
                {
                    tmp[0][x][y] = (1 - f[i - 1]) * p[0][x][y] +
                                   f[i - 1] * p[1][x][y];
                    tmp[1][x][y] = (1 - f[i - 1]) * (p[0][x][y] + (1 - p[0][x][y]) / cnt01) +
                                   f[i - 1] * (p[1][x][y] + (1 - p[1][x][y]) / cnt11);
                }
            }
        for(int t = 0; t < 2; t++)
            for(int x = 0; x < 10; x++)
                for(int y = 0; y < 10; y++)
                    p[t][x][y] = tmp[t][x][y];
    }

    for(int i = 1; i < n; i++)
        printf("%.12lf\n", dp[i][1] * f[i] + dp[i][0] * (1 - f[i]));

    cnt00 = cnt01 = cnt10 = cnt11 = 0, tmp00 = tmp01 = tmp10 = tmp11 = 0;
    for(int x = 1; x < 10; x++)
        for(int y = 1; y < 10; y++)
            if(x + y <= 8)
            {
                cnt00++, cnt10++;
                tmp00 += Cost(x, y, 0), tmp10 += Cost(x, y, 1);
            }
            else if(x + y == 9)
            {
                cnt00++, cnt11++;;
                tmp00 += Cost(x, y, 0), tmp11 += Cost(x, y, 1);;
            }
            else if(x + y >= 10)
            {
                cnt01++, cnt11++;
                tmp01 += Cost(x, y, 0), tmp11 += Cost(x, y, 1);
            }
    dp[n][0] += f[n - 1] * (dp[n - 1][1] + tmp10 / cnt10 + 1) +
                (1 - f[n - 1]) * (dp[n - 1][0] + tmp00 / cnt00);
    dp[n][1] += f[n - 1] * (dp[n - 1][1] + tmp11 / cnt11 + 1) +
                (1 - f[n - 1]) * (dp[n - 1][0] + tmp01 / cnt01);
    dp[n][1] += 1; // // write & mark & write next column

    DB ans = n + f[n] * (dp[n][1] + 1) + (1 - f[n]) * dp[n][0];
    printf("%.12lf\n", ans);
}

int main()
{
    ios::sync_with_stdio(0);
    input();
    solve();
    return 0;
}

Edited by author 01.03.2016 18:27