Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <stdio.h>
- #include <stdlib.h>
- #include <iostream>
- #include <algorithm>
- #include <string.h>
- #include <queue>
- #include <vector>
- #define ff first
- #define ss second
- using namespace std;
- double dp[5][10005];
- double prob[4][4][4];
- double f(int a, int b){
- if(a == 1) return 0;
- if(b == 0) return 1;
- if(dp[a][b] != -1) return dp[a][b];
- double ret = 0;
- if(a > 3){
- if(b >= 3)
- 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));
- else if(b == 2)
- ret = (prob[3][2][2] + prob[3][2][1]*f(a-1,b-1) + prob[3][2][0]*f(a-2,b));
- else
- ret = (prob[3][1][1] + prob[3][1][0]*f(a-1,b));
- }
- else if(a == 3){
- if(b >= 3)
- ret = (prob[2][3][2]*f(a,b-2) + prob[2][3][1]*f(a-1,b-1));
- else if(b == 2)
- ret = (prob[2][2][2] + prob[2][2][1]*f(a-1,b-1));
- else
- ret = (prob[2][1][1] + prob[2][1][0]*f(a-1,b));
- }
- else{
- if(b >= 3)
- ret = (prob[1][3][1]*f(a,b-1));
- else if(b == 2)
- ret = (prob[1][2][1]*f(a,b-1));
- else
- ret = (prob[1][1][1]);
- }
- return dp[a][b] = ret;
- }
- int main () {
- int n,m;
- prob[1][1][1] = (double)15/36;
- prob[1][1][0] = (double)21/36;
- prob[1][2][1] = (double)55/216;
- prob[1][2][0] = (double)161/216;
- prob[1][3][1] = (double)225/1296;
- prob[1][3][0] = (double)1071/1296;
- prob[2][1][1] = (double)125/216;
- prob[2][1][0] = (double)91/216;
- prob[2][2][2] = (double)295/1296;
- prob[2][2][1] = (double)420/1296;
- prob[2][2][0] = (double)581/1296;
- prob[2][3][2] = (double)979/7776;
- prob[2][3][1] = (double)1981/7776;
- prob[2][3][0] = (double)4816/7776;
- prob[3][1][1] = (double)855/1296;
- prob[3][1][0] = (double)441/1296;
- prob[3][2][2] = (double)2890/7776;
- prob[3][2][1] = (double)2611/7776;
- prob[3][2][0] = (double)2275/7776;
- prob[3][3][3] = (double)6420/46656;
- prob[3][3][2] = (double)10017/46656;
- prob[3][3][1] = (double)12348/46656;
- prob[3][3][0] = (double)17871/46656;
- scanf("%d%d", &n,&m);
- for(int i = 0; i <= 4; i++) dp[i][0] = 1;
- for(int i = 0; i <= m; i++) dp[1][i] = 0;
- for(int i = 2; i <= n; i++){
- for(int j = 1; j <= m; j++){
- double ret;
- int x = i%5;
- int a,b,c;
- a = x-3 < 0 ? 5+x-3:x-3;
- b = x-2 < 0 ? 5+x-2:x-2;
- c = x-1 < 0 ? 5+x-1:x-1;
- if(i > 3){
- if(j >= 3)
- 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];
- else if(j == 2)
- ret = prob[3][2][2] + prob[3][2][1]*dp[c][j-1] + prob[3][2][0]*dp[b][j];
- else
- ret = prob[3][1][1] + prob[3][1][0]*dp[c][j];
- }
- else if(i == 3){
- if(j >= 3)
- ret = prob[2][3][2]*dp[x][j-2] + prob[2][3][1]*dp[c][j-1];
- else if(j == 2)
- ret = prob[2][2][2] + prob[2][2][1]*dp[c][j-1];
- else
- ret = prob[2][1][1] + prob[2][1][0]*dp[c][j];
- }
- else{
- if(j >= 3)
- ret = prob[1][3][1]*dp[x][j-1];
- else if(j == 2)
- ret = prob[1][2][1]*dp[x][j-1];
- else
- ret = prob[1][1][1];
- }
- dp[x][j] = ret;
- }
- }
- printf("%.4lf\n", dp[n%5][m]);
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement