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 My submittion ID is 4115605. PS: This is the first time I have seen this message on TIMUS. My program should be correct. Edited by author 08.02.2012 21:20 1 -> 3.901234568 3 -> 11.127676543 4 -> 14.729570346 7 -> 25.468979219 29 -> 101.642021572 666 -> 2035.625369012 2011 -> 6070.641622553 5000 -> 15037.641622575 P.S. I have WA #4 As you can verify with brute-force, your answers are wrong. Right answers to your tests are: 1 -> 3.901234567901235 3 -> 11.127669135802471 4 -> 14.729542419753088 7 -> 25.468757517434465 29 -> 101.624893271458560 666 -> 2034.088837677804600 2011 -> 6069.098765418760200 5000 -> 15036.098765432045000 Thank you very much! It seems to be the precision problem in my first solution. But I don't understand why my program gives correct answers now. I just replaced the calculation of expected time of a group of combinations ( the total amount of them is 100 ) to calculation this for every combination separately on each iteration (of course, I did the same with array of probabilities). But I think the more very small numbers you store, the bigger precision troubles you have, isn't it? Oh my God, you described something very difficult =) My solution fills only two linear arrays in O(N)... I have an array P[10][10], where P[i][j] is the probability, that Feofan remembers the combination i,j (if i or j less, than 2, then P[i][j] = 1). Then I calculate the expected time for each such combination. So, you can assume I also have 2 arrays of length 100, and my algo O(k) :) I don't quite understand where do you need this array P[10][10]? - for any combination of digits you can easily calculate probability that he was already summing this before k-th position - it is 1-0.98^(k-1) for non-equal digits and 1-0.99^(k-1) for equal digits... Yes, it's true (except the combinations like 1-4). But I store this in array because of my own convenience :) Edited by author 20.05.2011 16:13 |
|