Codeforces 866C Gotta Go Fast - 动态规划 - 概率与期望

You're trying to set the record on your favorite video game. The game consists of N levels, which must be completed sequentially in order to beat the game. You usually complete each level as fast as possible, but sometimes finish a level slower. Specifically, you will complete the i-th level in either Fi seconds or Si seconds, where Fi < Si, and there's a Pi percent chance of completing it in Fi seconds. After completing a level, you may decide to either continue the game and play the next level, or reset the game and start again from the first level. Both the decision and the action are instant.

Your goal is to complete all the levels sequentially in at most R total seconds. You want to minimize the expected amount of time playing before achieving that goal. If you continue and reset optimally, how much total time can you expect to spend playing?

Input

The first line of input contains integers N and R , the number of levels and number of seconds you want to complete the game in, respectively. N lines follow. The ith such line contains integers Fi, Si, Pi (1 ≤ Fi < Si ≤ 100, 80 ≤ Pi ≤ 99), the fast time for level i, the slow time for level i, and the probability (as a percentage) of completing level i with the fast time.

Output

Print the total expected time. Your answer must be correct within an absolute or relative error of 10 - 9.

Formally, let your answer be a, and the jury's answer be b. Your answer will be considered correct, if .

Examples

input

1 82 8 81

output

3.14

input

2 3020 30 803 9 85

output

31.4

input

4 31963 79 8979 97 9175 87 8875 90 83

output

314.159265358

Note

In the first example, you never need to reset. There's an 81% chance of completing the level in 2 seconds and a 19% chance of needing 8 seconds, both of which are within the goal time. The expected time is 0.81·2 + 0.19·8 = 3.14.

In the second example, you should reset after the first level if you complete it slowly. On average it will take 0.25 slow attempts before your first fast attempt. Then it doesn't matter whether you complete the second level fast or slow. The expected time is 0.25·30 + 20 + 0.85·3 + 0.15·9 = 31.4.

　　题目大意 一个人打游戏，需要不超过$R$秒通过$n$关，第$i$关有$P_{i}$的概率用$F_{i}$秒通过，$\left(1 - P_{i}\right)$的概率用$S_{i}$通过（$F_{i} < S_{i}$），通过每一关可以选择重置游戏，然后从头开始，或者去打下一关。问不超过$R$秒通过所有关卡的期望耗时。

　　转移是显然的。（如果这个都不会，请自定百度“概率dp入门题”）

　　然后发现转移有环，还要做决策？

　　然后列方程吧。。开心地发现不会解。

　　可惜这里是信息学竞赛，不是数学竞赛。由于转移都需要 dp[][] 但是开始不知道它，所以考虑二分它，然后和推出来的 dp[][] 作比较。

　　经过各种瞎猜和乱搞，可以发现一个神奇的事情

　　然后就可根据它来确定一次check后，二分的范围。

　　另外，由于坑人的精度问题，所以最好不要写while (l + eps < r) ，总之我这么写各种因为精度问题的TLE来了。

Code

 /**
  * Codeforces
  * Problem#866C
  * Accepted
  * Time: 62ms
  * Memory: 4316k
  */
 #include <bits/stdc++.h>
 using namespace std;
 typedef bool boolean;

 ;
 ;

 int n, R;
 int *fs, *ss;
 double *ps;

 inline void init() {
     scanf("%d%d", &n, &R);
     fs = )];
     ss = )];
     ps = )];
     ; i <= n; i++) {
         scanf("%d%d", fs + i, ss + i);
         cin >> ps[i];
         ps[i] *= 0.01;
     }
 }

 boolean vis[][];
 ][];

 double dfs(int d, int t, double &mid) {
     );
     if(vis[d][t])    return f[d][t];
     vis[d][t] = true;
     f[d][t] = (dfs(d + , t + fs[d + ], mid) + fs[d + ]) * ps[d + ] + (dfs(d + , t + ss[d + ], mid) + ss[d + ]) * ( - ps[d + ]);
     if(mid < f[d][t])    f[d][t] = mid;
     return f[d][t];
 }

 double dp(double mid) {
     memset(vis, false, sizeof(vis));
     , , mid);
 }

 inline void solve() {
     , r = 1e9;
     ; i < binary_lim; i++) {
         ;
         if(dp(mid) < mid)    r = mid;
         else    l = mid;
     }
     printf("%.9lf", l);
 }

 int main() {
     init();
     solve();
     ;
 }

巴特西

Codeforces 866C Gotta Go Fast - 动态规划 - 概率与期望 - 二分答案

Code

最新文章

热门文章