【Codeforces 498B】 B. Name That Tune （概率DP）

B. Name That Tune

time limit per test

1 second

memory limit per test

256 megabytes

input

standard input

output

standard output

It turns out that you are a great fan of rock band AC/PE. Peter learned that and started the following game: he plays the first song of the list of n songs of the group, and you have to find out the name of the song. After you tell the song name, Peter immediately plays the following song in order, and so on.

The i-th song of AC/PE has its recognizability pi. This means that if the song has not yet been recognized by you, you listen to it for exactly one more second and with probability of pi percent you recognize it and tell it's name. Otherwise you continue listening it. Note that you can only try to guess it only when it is integer number of seconds after the moment the song starts playing.

In all AC/PE songs the first words of chorus are the same as the title, so when you've heard the first ti seconds of i-th song and its chorus starts, you immediately guess its name for sure.

For example, in the song Highway To Red the chorus sounds pretty late, but the song has high recognizability. In the song Back In Blue, on the other hand, the words from the title sound close to the beginning of the song, but it's hard to name it before hearing those words. You can name both of these songs during a few more first seconds.

Determine the expected number songs of you will recognize if the game lasts for exactly T seconds (i. e. you can make the last guess on the second T, after that the game stops).

If all songs are recognized faster than in T seconds, the game stops after the last song is recognized.

Input

The first line of the input contains numbers n and T (1 ≤ n ≤ 5000, 1 ≤ T ≤ 5000), separated by a space. Next n lines contain pairs of numbers pi and ti (0 ≤ pi ≤ 100, 1 ≤ ti ≤ T). The songs are given in the same order as in Petya's list.

Output

Output a single number — the expected number of the number of songs you will recognize in T seconds. Your answer will be considered correct if its absolute or relative error does not exceed 10 - 6.

Examples

input

2 2
50 2
10 1

output

1.500000000

input

2 2
0 2
100 2

output

1.000000000

input

3 3
50 3
50 2
25 2

output

1.687500000

input

2 2
0 2
0 2

output

1.000000000

【分析】

　　这题感觉挺难想的啊？

　　f[i][j]表示j秒的时候正在听第i首歌（前面的认出来，i正在听）的概率。

　　不考虑t[i]的时候是f[i][j]=f[i-1][j-1]*p[i-1]+f[i][j-1]*(1-p[i])

　　考虑了t[i]说明f[i][j]不会转到f[i][j+t[i]]而是f[i+1][j]

　　所以特判这一部分的转移。

　　【然后比较迷人的一点是要用“错的f更新f”？】

　　其实正确的转移状态应该是f[i][j]->f[i][j+k](1<=k<t[i])

　　但是每次只加一然后累计过去的话少一重循环，说明了f还是一个运输工具【可以这样说吧？不断向j+1的地方运输嘛。。

　　你的f还有别人那里运过来的东西，应该由别人累计减掉，你只应该减掉你自己那部分，所以要用g记录，用g更新【我只能这样理解这一层了

　　最后加一首歌，若正在播这首说明前一秒已认出前面的所有歌。

　　可以模这个题解：http://blog.csdn.net/clove_unique/article/details/62089010

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
#define Maxn 5010

double p[Maxn];
int t[Maxn];
double f[Maxn][Maxn],g[Maxn];

double qpow(double p,int b)
{
    double ans=1.0;
    while(b)
    {
        if(b&1) ans*=p;
        p*=p;
        b>>=1;
    }
    return ans;
}

int main()
{
    int n,T;
    scanf("%d%d",&n,&T);
    for(int i=1;i<=n;i++)
    {
        scanf("%lf%d",&p[i],&t[i]);
        p[i]/=100.0;
    }
    f[1][1]=1;p[n+1]=0;t[n+1]=5000;
    for(int i=1;i<=n+1;i++)
    {
        double P=qpow(1-p[i],t[i]);
        for(int j=1;j<=T+1;j++) g[j]=f[i][j];
        for(int j=1;j<=T+1;j++)
        {
            f[i][j+1]+=f[i][j]*(1-p[i]);
            f[i+1][j+1]+=f[i][j]*p[i];
            if(j+t[i]<=T+1)
            {
                f[i][j+t[i]]-=g[j]*P;
                f[i+1][j+t[i]]+=g[j]*P;
            }
        }
    }
    double ans=0;
    for(int i=1;i<=n+1;i++) ans+=f[i][T+1]*(i-1);
    printf("%.9lf
",ans);
    return 0;
}

2017-04-22 08:05:14