Advertisement
Guest User

Untitled

a guest
Jul 25th, 2016
220
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 3.15 KB | None | 0 0
  1. #include <stdio.h>
  2. #include <stdlib.h>
  3. #include <iostream>
  4. #include <algorithm>
  5. #include <string.h>
  6. #include <queue>
  7. #include <vector>
  8.  
  9. #define ff first
  10. #define ss second
  11.  
  12. using namespace std;
  13.  
  14. double dp[5][10005];
  15. double prob[4][4][4];
  16.  
  17. double f(int a, int b){
  18.     if(a == 1) return 0;
  19.     if(b == 0) return 1;
  20.     if(dp[a][b] != -1) return dp[a][b];
  21.     double ret = 0;
  22.     if(a > 3){
  23.         if(b >= 3)
  24.             ret = (prob[3][3][3]*f(a,b-3) + prob[3][3][2]*f(a-1,b-2) + prob[3][3][1]*f(a-2,b-1) + prob[3][3][0]*f(a-3,b));
  25.         else if(b == 2)
  26.             ret = (prob[3][2][2] + prob[3][2][1]*f(a-1,b-1) + prob[3][2][0]*f(a-2,b));
  27.         else
  28.             ret = (prob[3][1][1] + prob[3][1][0]*f(a-1,b));
  29.     }
  30.     else if(a == 3){
  31.         if(b >= 3)
  32.             ret = (prob[2][3][2]*f(a,b-2) + prob[2][3][1]*f(a-1,b-1));
  33.         else if(b == 2)
  34.             ret = (prob[2][2][2] + prob[2][2][1]*f(a-1,b-1));
  35.         else
  36.             ret = (prob[2][1][1] + prob[2][1][0]*f(a-1,b));
  37.     }
  38.     else{
  39.         if(b >= 3)
  40.             ret = (prob[1][3][1]*f(a,b-1));
  41.         else if(b == 2)
  42.             ret = (prob[1][2][1]*f(a,b-1));
  43.         else
  44.             ret = (prob[1][1][1]);
  45.     }
  46.     return dp[a][b] = ret;
  47. }
  48.  
  49. int main () {
  50.     int n,m;
  51.  
  52.     prob[1][1][1] = (double)15/36;
  53.     prob[1][1][0] = (double)21/36;
  54.  
  55.     prob[1][2][1] = (double)55/216;
  56.     prob[1][2][0] = (double)161/216;
  57.  
  58.     prob[1][3][1] = (double)225/1296;
  59.     prob[1][3][0] = (double)1071/1296;
  60.  
  61.     prob[2][1][1] = (double)125/216;
  62.     prob[2][1][0] = (double)91/216;
  63.  
  64.     prob[2][2][2] = (double)295/1296;
  65.     prob[2][2][1] = (double)420/1296;
  66.     prob[2][2][0] = (double)581/1296;
  67.  
  68.     prob[2][3][2] = (double)979/7776;
  69.     prob[2][3][1] = (double)1981/7776;
  70.     prob[2][3][0] = (double)4816/7776;
  71.  
  72.     prob[3][1][1] = (double)855/1296;
  73.     prob[3][1][0] = (double)441/1296;
  74.  
  75.     prob[3][2][2] = (double)2890/7776;
  76.     prob[3][2][1] = (double)2611/7776;
  77.     prob[3][2][0] = (double)2275/7776;
  78.  
  79.     prob[3][3][3] = (double)6420/46656;
  80.     prob[3][3][2] = (double)10017/46656;
  81.     prob[3][3][1] = (double)12348/46656;
  82.     prob[3][3][0] = (double)17871/46656;
  83.  
  84.     scanf("%d%d", &n,&m);
  85.  
  86.     for(int i = 0; i <= 4; i++) dp[i][0] = 1;
  87.     for(int i = 0; i <= m; i++) dp[1][i] = 0;
  88.  
  89.     for(int i = 2; i <= n; i++){
  90.         for(int j = 1; j <= m; j++){
  91.             double ret;
  92.             int x = i%5;
  93.             int a,b,c;
  94.             a = x-3 < 0 ? 5+x-3:x-3;
  95.             b = x-2 < 0 ? 5+x-2:x-2;
  96.             c = x-1 < 0 ? 5+x-1:x-1;
  97.             if(i > 3){
  98.                 if(j >= 3)
  99.                     ret = prob[3][3][3]*dp[x][j-3] + prob[3][3][2]*dp[c][j-2] + prob[3][3][1]*dp[b][j-1] + prob[3][3][0]*dp[a][j];
  100.                 else if(j == 2)
  101.                     ret = prob[3][2][2] + prob[3][2][1]*dp[c][j-1] + prob[3][2][0]*dp[b][j];
  102.                 else
  103.                     ret = prob[3][1][1] + prob[3][1][0]*dp[c][j];
  104.             }
  105.             else if(i == 3){
  106.                 if(j >= 3)
  107.                     ret = prob[2][3][2]*dp[x][j-2] + prob[2][3][1]*dp[c][j-1];
  108.                 else if(j == 2)
  109.                     ret = prob[2][2][2] + prob[2][2][1]*dp[c][j-1];
  110.                 else
  111.                     ret = prob[2][1][1] + prob[2][1][0]*dp[c][j];
  112.             }
  113.             else{
  114.                 if(j >= 3)
  115.                     ret = prob[1][3][1]*dp[x][j-1];
  116.                 else if(j == 2)
  117.                     ret = prob[1][2][1]*dp[x][j-1];
  118.                 else
  119.                     ret = prob[1][1][1];
  120.             }
  121.             dp[x][j] = ret;
  122.         }
  123.     }
  124.     printf("%.4lf\n", dp[n%5][m]);
  125.     return 0;
  126.    
  127. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement