Question (in Chinese): http://ac.jobdu.com/problem.php?pid=1360
Question Name: Dices Probability
Question Description: You have some customized dices. Find the three most possible sum of the dices, if you roll them.
Input: the input might contain multiple test cases. Each line, as a test case, contains two positive integers N (0 <= N <= 10) and M (6 <= M <= 8). N is the count of the dices. And M is the maximum point of the dice. So the dice’s value is [1, M], both inclusive. When get the N being 0, quit the program.
Output: print the three most possible sum of the dices, and their probability. Only consider and show the two digits after decimal point.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 | Input: 1 6 4 6 3 7 Output: 1 0.17 2 0.17 3 0.17 13 0.11 14 0.11 15 0.11 12 0.11 10 0.10 11 0.10 |
The solution is:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 | /*---------------------------------------------------------------- * Author: Sheng Yu - codesays.com * Written: 09/09/2014 * Last updated: 09/09/2014 * * Filename: DicesProbability.java * Compilation: javac DicesProbability.java * Execution: java DicesProbability * JDK Used: 1.7 *----------------------------------------------------------------*/ import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.io.StreamTokenizer; /** * The utility to rotate a string. * @author Sheng Yu codesays.com */ public class DicesProbability { /** * Returns the closest int to the argument. Place it to fix the bug in * Java 6, which is used in Jobdu OJ system. * http://stackoverflow.com/questions/9902968/why-does-math-round0-49999999999999994-return-1 * @param d the original float number. * @return the closest int to the argument. */ public static int round(double d) { if (d != 0x1.fffffffffffffp-2) { // a is not the greatest double value less than 0.5 return (int)Math.floor(d + 0.5d); } else { return 0; } } /** * Given count of dices, whose value is in range [1, dice]. Show the three most * possible result. * @param count the number of dices. * @param dice the maximum value of each dice. */ public static void threeHighProbability(int count, int dice) { int[] occurrence = new int[count * dice + 1]; int temp = 0; // Roll the dice one by one. occurrence[0] = 1; for (int round = 0; round < count; ++round) { for (int total = (round + 1) * dice; total >= 1; --total) { temp = 0; for (int pre = 1; pre <= dice; ++pre) { if (total - pre < 0) break; else temp += occurrence[total - pre]; } occurrence[total] = temp; } // After (round + 1) rolls, we have at least (round + 1) points. occurrence[round] = 0; } // Calculate the probability. int sum = 0; for (int i : occurrence) sum += i; for (int i = count; i < occurrence.length; ++i) { // occurrence[i] = j means the probability is j%. occurrence[i] = round(occurrence[i] * 1.0 / sum * 100); } // Find the top 3 most possible results. int[] top3 = new int[] {0, 0, 0}; for (int i = count; i < occurrence.length; ++i) { if (occurrence[i] > occurrence[top3[0]]) { top3[2] = top3[1]; top3[1] = top3[0]; top3[0] = i; } else if (occurrence[i] > occurrence[top3[1]]) { top3[2] = top3[1]; top3[1] = i; } else if (occurrence[i] > occurrence[top3[2]]) { top3[2] = i; } else { assert true; } } // Output the top 3 choices. System.out.print(String.format("%d 0.%02dn",top3[0], occurrence[top3[0]])); System.out.print(String.format("%d 0.%02dn",top3[1], occurrence[top3[1]])); System.out.print(String.format("%d 0.%02dn",top3[2], occurrence[top3[2]])); return; } /** * Stub for test. * @param args the command line arguments. * @throws IOException when input gets error. */ public static void main(String[] args) throws IOException { StreamTokenizer st = new StreamTokenizer(new BufferedReader( new InputStreamReader(System.in))); int count = 0; int dice = 0; boolean firstTest = true; while (st.nextToken() != StreamTokenizer.TT_EOF) { count = (int) st.nval; if (count == 0) break; st.nextToken(); dice = (int) st.nval; if (firstTest) firstTest = false; else System.out.println(); threeHighProbability(count, dice); } return; } } |