[UVA][JAVA][dp] 10238 - Throw the Dice＠Morris' Blog｜PChome Online 人新台

Morris' Blog 我在摸索我存在的意、生命的意、涵及值。有真正神手般的害，套用模式是大部分的情。那害的我存在的意何，托出神的存在？有候不能怪人不我，我已始省思，什我有人的原因，而是全要靠人。有候我我不同，那是因我做不到很多人能到的事情。我不到、玩不起、得不明、理解得不多，我缺少的文能力，就是一切一切能的判定。此，我不得能做些人有助的事情。我知道我自己是不服的性格，但在我不得不。我有能力，因此我必。我到底世界作什？充不定性，而我是法出拔萃，想一般人似乎也回不了了。越大的挑需要越力的支持，而我的支持是什？最近人，但都是失的局，人能接受，不需要言，不需要通，一切所想都表不出。
49的鼓 6站台

2012-10-29 07:17:40| 人1,172| 回0 | 上一篇 | 下一篇

<-- start of blogbody -->

[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 = F^N). Here a/b means the probability value. Note that we don’t need thefloating 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);
       }
   }
}