Algorithm


problem Link :  https://onlinejudge.org/index.php?option=onlinejudge&Itemid=8&page=show_problem&problem=1700 

n common cubic dice are thrown. What is the probability that the sum of all thrown dice is at least x? Input The input file contains several test cases. Each test case consists two integers n (1 ≤ n ≤ 24) and x (0 ≤ x < 150). The meanings of n and x are given in the problem statement. Input is terminated by a case where n =0 and x =0. This case should not be processed. Output For each line of input produce one line of output giving the requested probability as a proper fraction in lowest terms in the format shown in the sample output. All numbers appearing in output are representable in unsigned 64-bit integers. The last line of input contains two zeros and it should not be processed.

Sample Input 3 9 1 7 24 24 15 76 24 56 24 143 23 81 7 38 0 0

Sample Output 20/27 0 1 11703055/78364164096 789532654692658645/789730223053602816 25/4738381338321616896 1/2 55/46656

Code Examples

#1 Code Example with C Programming

Code - C Programming

#include <bits/stdc++.h>

using namespace std;
#define ll long long

vector < vector<ll>> memo(25, vector < ll>(151,-1));

ll solve(int n, int x) {
    if(n == 0)
        return x == 0 ? 1 : 0;
    if(memo[n][x] != -1) return memo[n][x];
    ll res = 0;
    for(int i=1;i<=6;i++) {
        // can't go below 0, already meet requirement
        int nextX = max(x - i, 0);
        res += solve(n-1, nextX);
    }
    memo[n][x] = res;
    return res;
}

ll gcd(ll a, ll b) {
    return b == 0 ? a : gcd(b, a%b);
}

int main()
{
    int n,x;
    while(scanf("%d %d",&n,&x),(n+x)) {
        ll numerator = solve(n,x);
        ll denominator = floor(pow(6, n));
        if(numerator == denominator) {
            printf("1\n");
        } else if(numerator != 0) {
            ll d = gcd(numerator, denominator);
            numerator /= d;
            denominator /= d;
            printf("%lld/%lld\n", numerator, denominator);
        } else {
            printf("0\n">;
        }
    }
}
 
Copy The Code & Try With Live Editor

Input

x
+
cmd
3 9
1 7
24 24
15 76
24 56
24 143
23 81
7 38
0 0

Output

x
+
cmd
20/27
0
1
11703055/78364164096
789532654692658645/789730223053602816
25/4738381338321616896
1/2
55/
Advertisements

Demonstration


UVA Online Judge solution - 10759-Dice Throwing - UVA Online Judge solution in C,C++,java 

Previous
UVA Online Judge solution - 10739-String to Palindrome - UVA Online Judge solution in C,C++,java
Next
UVA Online Judge solution - 10763-Foreign Exchange - UVA Online Judge solution in C,C++,java