2018 网易校招 骰子游戏

题目描述

小易参加了一个骰子游戏,这个游戏需要同时投掷n个骰子,每个骰子都是一个印有数字1~6的均匀正方体。 小易同时投掷出这n个骰子,如果这n个骰子向上面的数字之和大于等于x,小易就会获得游戏奖励。 小易想让你帮他算算他获得奖励的概率有多大。

输入描述:

输入包括两个正整数n和x(1 ≤ n < 25, 1 ≤ x < 150),分别表示骰子的个数和可以获得奖励的最小数字和。

输出描述:

输出小易可以获得奖励的概率。 如果概率为1,输出1,如果概率为0,输出0,其他以最简分数(x/y)的形式输出。

示例1

输入

3 9

输出

20/27

首先用动态规化求出方案数，在计算出概率，注意特判掉特殊情况

#include <iostream> #include <cmath> using namespace std; const int N = 1000; typedef long long LL; LL dp[N][N]; // dp[i][j] 表示前掷i个骰子，之和等于j的方案数 LL gcd(LL a, LL b) { //求最大公约数 LL temp; while (b > 0) { temp = a % b; a = b; b = temp; } return a; } int main() { int n, x; cin >> n >> x; if(x==n){ cout<<1<<endl; return 0; } LL count = pow(6, n); if(x>count){ cout<<0<<endl; return 0; } for (int i = 1; i <= 6; i++) dp[1][i] = 1; // 边界条件 for (int i = 2; i <= n; i++) { for (int j = 1; j <= 6 * i; j++) { for (int k = 1; k <= 6; k++) { if (j > k) { dp[i][j] += dp[i - 1][j - k]; } } } } LL sum=0; for (int i = x; i <= 6 * n; i++) sum += dp[n][i]; if(sum==0){ cout<<0<<endl; return 0; } LL g = gcd(count, sum); cout << sum / g << "/" << count / g << endl; }