24h購物| | PChome| 登入
2012-10-29 07:17:40| 人氣1,048| 回應0 | 上一篇 | 下一篇

[UVA][JAVA][dp] 10238 - Throw the Dice

推薦 0 收藏 0 轉貼0 訂閱站台

Problem C
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);            
        }
    }
}

台長: Morris
人氣(1,048) | 回應(0)| 推薦 (0)| 收藏 (0)| 轉寄
全站分類: 不分類 | 個人分類: UVA |
此分類下一篇:[UVA] 10895 - Matrix Transpose
此分類上一篇:[UVA][dp] 542 - France '98

是 (若未登入"個人新聞台帳號"則看不到回覆唷!)
* 請輸入識別碼:
請輸入圖片中算式的結果(可能為0) 
(有*為必填)
TOP
詳全文