HDU-5194-DZY Loves Balls(BestCoder Round # 35 )

DZY Loves Balls
Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/65536 K (Java/Others) Total Submission(s): 374    Accepted Submission(s): 205
Problem Description
There are 
n  black balls and 
m  white balls in the big box.
Now, DZY starts to randomly pick out the balls one by one. It forms a sequence 
S . If at the 
i -th operation, DZY takes out the black ball, 
Si=1 , otherwise 
Si=0 .
DZY wants to know the expected times that '01' occurs in 
S .
 
Input
The input consists several test cases. (
TestCase≤150 )
The first line contains two integers, 
n , 
m(1≤n,m≤12)
 
Output
For each case, output the corresponding result, the format is 
p/q (
p  and 
q  are coprime)
 
Sample Input

   
   
   
   

    
    
    
    1 1
2 3
   
   
   
   

 
Sample Output

   
   
   
   

    
    
    
    1/2
6/5


    
    
    
    
 
     
 
      Hint 
     
Case 1: S='01' or S='10', so the expected times = 1/2 = 1/2 Case 2: S='00011' or S='00101' or S='00110' or S='01001' or S='01010' or S='01100' or S='10001' or S='10010' or S='10100' or S='11000', so the expected times = (1+2+1+2+2+1+1+1+1+0)/10 = 12/10 = 6/5 
    
    
    
    
     
   
   
   
   

 
Source
BestCoder Round #35
 
Recommend
hujie   |   We have carefully selected several similar problems for you:   5197  5196  5195  5193  5192 
BestCoder解析:

Problem A - DZY Loves Balls
        。 
    
     i(1≤i<n+m)
          0， 
    
     i+1
          1    
    
     mn+m×nn+m−1
    ，        
    
     ∑i=1n+m−1mn+m×nn+m−1=nmn+m
    
                 ，           01 ，    AC 。            gcd，    。

n個の黒球、m個の白球、1は取り出したのが黒球、0は取り出したのが白球であることを示す.
この問題の最良の方法は問題の法則を探し出すことであり,すなわちi(1<=iこの条件を満たすために、S列に出現する「01」列の位置が要求されるが、「0」は末尾であってはならず、「1」は先頭であってはならない.
i+1番目の位置に1が現れる確率は、(黒球が現れる(1が現れる)確率)*(i番目の位置に現れる確率)である.
しかし、n+m-1個の位置に1が現れるので、すべての位置における確率を加算したい.
等価=  m/(n+m)   *    n/(n+m-1)    *    (n+m-1)  = n*m/(n+m).

import java.io.*;
import java.util.*;

public class Main
{

	public static void main(String[] args)
	{
		Scanner input = new Scanner(System.in);
		while (input.hasNext())
		{
			int n = input.nextInt();
			int m = input.nextInt();
			int temp = GCD(n * m, n + m);
			System.out.println(n * m / temp + "/" + (n + m) / temp);
		}
	}

	public static int GCD(int x, int y)
	{
		if (x < y)
			return GCD(y, x);
		while (x % y != 0)
		{
			int temp = x % y;
			x = y;
			y = temp;
		}
		return y;
	}
}