[UVA][JAVA][dp] 10238 - Throw the Dice
Throw the Dice!
Input: standard input
Output: standard output
Time Limit: 30 seconds
Memory Limit: 32 MB
In the pictures below, you can see several types of Dices. It is very easy to assume that they are used in many different types of games. In this problem, the face of the dices will be like those on the first figure, that means each will have some dots it each face, which will indicate the value of that particular face. But the looks of the dices will be like those on the second figure, that means each dice may have 2, 3, 4, 5 up to 50 different faces. A dice with p faces have face values 1, 2, 3 … p. When a dice is thrown all the faces are equally likely to come on top. For example an ordinary dice in figure-1 has face values 1, 2, 3, 4, 5, 6 and the probability that face with value 1 will be on top is 1/6. The same is the probability for the other faces coming on top.
 |
 |
| Figure 1: Two conventional dices | Figure 2: Dices of different shape |
The situation becomes complicated when you throw a dice more than once dice. For example when you throw a dice twice, for any arbitrary incident the summation of the top two faces can be within the range (inclusive) 2...12. But their probability is not equally likely or 1/12. The probability that the sum will be two is 1/36, but the probability that some will be three is 2/36 and so on. Given the description of a dice throw, that’s how many faces it have, how many throws will be made and value for the sum, you will have to find the probability of obtaining that sum.
Input
The input will contain several lines of input. Each line contains three integers F (The number of faces of the dice thrown, 1<=F<=50), N (The number of throws and 0<=N<=50) and S (The summation value for which you to find out the probability, 0<S<=4000).
Output
For each line of input you will have to produce one line of output which will be of the form a/b (Here b = FN). Here a/b means the probability value. Note that we don’t need the floating point value of probability.
Sample Input
6 2 2
6 2 3
6 3 10
Sample Output
1/36
2/36
27/216
import java.math.BigInteger;
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner cin = new Scanner(System.in);
while(cin.hasNext()) {
int F, N, S;
F = cin.nextInt();
N = cin.nextInt();
S = cin.nextInt();
if(S < N || S > N*F)
System.out.print("0");
else {
BigInteger[][] dp = new BigInteger[N+1][N*F+1];
dp[0][0] = BigInteger.valueOf(1);
for(int i = 1; i <= N; i++) {
for(int j = i; j <= i*F; j++) {
dp[i][j] = BigInteger.valueOf(0);
for(int k = 1; k <= F; k++) {
if(j-k >= 0 && j-k >= i-1 && j-k <= (i-1)*F) {
dp[i][j] = dp[i][j].add(dp[i-1][j-k]);
}
}
}
}
System.out.print(dp[N][S]);
}
BigInteger den = BigInteger.valueOf(F).pow(N);
System.out.println("/" + den);
}
}
}