lightoj 1064 - Throwing Dice

n common cubic dice are thrown. What is the probability that the sum of all thrown dice is at least x?

Input

Input starts with an integer T (≤ 200), denoting the number of test cases.

Each test case contains two integers n (1 ≤ n < 25) and x (0 ≤ x < 150). The meanings of n and x are given in the problem statement.

Output

For each case, output the case number and the probability in 'p/q' form where p and q are relatively prime. If q equals 1 then print p only.

#include<cmath>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define inf 1e9
#define LL long long
using namespace std;LL dp[30][160];
LL gcd(LL a,LL b)
{if(b == 0)return a;elsereturn gcd(b,a%b);
}int main(void)
{int T,n,x,i,j,k;scanf("%d",&T);int cas = 1;while(T--){scanf("%d%d",&n,&x);memset(dp,0,sizeof(dp));dp[0][0] = 1;LL sum = 1;for(i=1;i<=n;i++){sum *= 6;for(j=1;j<=i*6;j++){for(k=1;k<=6;k++){if(j < k)break;dp[i][j] += dp[i-1][j-k];}}}LL ans = 0;for(i=x;i<=n*6;i++)ans += dp[n][i];printf("Case %d: ",cas++);if(ans == 0){printf("0\n");continue;}if(ans == sum){printf("1\n");continue;}LL t = gcd(ans,sum);printf("%lld/%lld\n",ans/t,sum/t);}
}