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