首页 > 专题系列 > Java解POJ > POJ 1322 Chocolate [解题报告] Java
2013
11-09

POJ 1322 Chocolate [解题报告] Java

Chocolate

问题描述 :

In 2100, ACM chocolate will be one of the favorite foods in the world.

“Green, orange, brown, red…”, colorful sugar-coated shell maybe is the most attractive feature of ACM chocolate. How many colors have you ever seen? Nowadays, it’s said that the ACM chooses from a palette of twenty-four colors to paint their delicious candy bits.

One day, Sandy played a game on a big package of ACM chocolates which contains five colors (green, orange, brown, red and yellow). Each time he took one chocolate from the package and placed it on the table. If there were two chocolates of the same color on the table, he ate both of them. He found a quite interesting thing that in most of the time there were always 2 or 3 chocolates on the table.

Now, here comes the problem, if there are C colors of ACM chocolates in the package (colors are distributed evenly), after N chocolates are taken from the package, what’s the probability that there is exactly M chocolates on the table? Would you please write a program to figure it out?

输入:

The input file for this problem contains several test cases, one per line.

For each case, there are three non-negative integers: C (C <= 100), N and M (N, M <= 1000000).

The input is terminated by a line containing a single zero.

输出:

The output should be one real number per line, shows the probability for each case, round to three decimal places.

样例输入:

5 100 2

0

样例输出:

0.625 

解题代码:

//* @author: 
import java.util.*;
 public class Main{
  public static void main(String args[]){
      
      Scanner in=new Scanner(System.in);
     
      while(true){
       int c=in.nextInt();
       if(c==0) break;
       int n=in.nextInt();
       int m=in.nextInt();
       double arr[][]=new double[1002][101];
        if (m>c||m>n){   
         System.out.printf("0.000\n");
         continue;
        }
        if (n>1000) {
          if ((n%2)!=0) n = 1001;
          else     n = 1000;
        }
              
         arr[0][0] = 1;
         for (int i=1;i<=n;++i){
          arr[i][1] += arr[i-1][0];
          arr[i][c-1] += arr[i-1][c];
          for (int j = 1 ; j < c ; j++){
            arr[i][j-1] += arr[i-1][j] * j / c;
            arr[i][j+1] += arr[i-1][j] * (c-j) / c;       
          }
         }
         System.out.printf("%.3f\n",arr[n][m]);
        }
   }
}

  1. 很高兴你会喜欢这个网站。目前还没有一个开发团队,网站是我一个人在维护,都是用的开源系统,也没有太多需要开发的部分,主要是内容整理。非常感谢你的关注。

  2. 给你一组数据吧:29 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 1000。此时的数据量还是很小的,耗时却不短。这种方法确实可以,当然或许还有其他的优化方案,但是优化只能针对某些数据,不太可能在所有情况下都能在可接受的时间内求解出答案。