hdu 4405 Aeroplane chess

 1 #include<iostream>
 2 #include<string>
 3 #include<cstdio>
 4 #include<vector>
 5 #include<queue>
 6 #include<stack>
 7 #include<algorithm>
 8 #include<cstring>
 9 #include<stdlib.h>
10 using namespace std;
11 #define pb push_back
12 struct node{
13     int x,y;
14 }p[1010];
15 int cmp(node a,node b){
16     return a.x<b.x;
17 }
18 int main()
19 {
20     int n,m;
21     while(cin>>n>>m,n+m){
22         double dp[101010];
23         memset(dp,0,sizeof(dp));
24         for(int i=0;i<m;i++)
25             scanf("%d%d",&p[i].x,&p[i].y);
26         sort(p,p+m,cmp);
27         int cnt=m-1;
28         for(int i=n-1;i>=0;i--){
29               dp[i]=1;
30               if(cnt>=0&&i==p[cnt].x){
31                dp[i]=dp[p[cnt].y];
32                cnt--;
33                continue;
34               }
35               for(int j=6;j>=1;j--)
36                 dp[i]+=1.0/6*dp[i+j];
37         }
38         printf("%.4f\n",dp[0]);
39     }
40 }