ENG  RUS Timus Online Judge
Online Judge
Problems
Authors
Online contests
Site news
Webboard
Problem set
Submit solution
Judge status
Guide
Register
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules
back to board

## Discussion of Problem 1831. Tsyfirkin's Lesson

HELP! I don't where i wrong. I have spend several days on it.
Posted by SYFT 1 Mar 2016 11:44
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