当前位置:首页 » Project Euler » 详细页

Disc game prize fund 题号:121 难度: 35 中英对照

A bag contains one red disc and one blue disc. In a game of chance a player takes a disc at random and its colour is noted. After each turn the disc is returned to the bag, an extra red disc is added, and another disc is taken at random.

The player pays £1 to play and wins if they have taken more blue discs than red discs at the end of the game.

If the game is played for four turns, the probability of a player winning is exactly 11/120, and so the maximum prize fund the banker should allocate for winning in this game would be £10 before they would expect to incur a loss. Note that any payout will be a whole number of pounds and also includes the original £1 paid to play the game, so in the example given the player actually wins £9.

Find the maximum prize fund that should be allocated to a single game in which fifteen turns are played.

Solution

设第$n$次抽取后,记录了$k$个蓝色球的概率为$p(n,k)$,则抽取前有$n$个红球和$1$个篮球: $$p(n,k)= \frac{1}{n+1} \left[ p(n-1,k) \times n + p(n-1,k-1) \right]$$ 两侧同时乘以$(n+1)\times n!$,设$a(n,k)=(n+1)! \times p(n,k)$,则将上式变化为: $$a(n,k)=n \times x(n-1,k)+x(n-1,k-1)$$ 边缘情况为$a(x,x)=1 \forall x \geq 0, \quad a(x,0)=0 \forall x > 0$

Code

import java.math.*;
public final class p121 {
    public static void main(String[] args) {
        long start=System.nanoTime();
        String result = run();        
        long end=System.nanoTime();
        System.out.println(result);
        System.out.println( (end-start)/1000000 + "ms" );
    }
    
    static public String run(){
    	BigInteger a[][]=new BigInteger[22][22];
    	for(int i=0;i<22;i++) a[0][i]=BigInteger.ZERO;
    	final int N=15;
    	a[0][0]=BigInteger.ONE;
    	for(int i=1;i<=N;i++){
    		a[i][0]=BigInteger.valueOf(i).multiply(a[i-1][0]);
    		for(int j=1;j<i;j++){
    			a[i][j]=BigInteger.valueOf(i).multiply(a[i-1][j]).add(
    					a[i-1][j-1]);
    		}
    		a[i][i]=BigInteger.ONE;
    	}
    	BigInteger sum=BigInteger.ZERO,cnt=BigInteger.ZERO;
    	for(int j=0;j<=N;j++){
    		sum=sum.add(a[N][j]);
    		int red=N-j;
    		if(j>red) cnt=cnt.add(a[N][j]);
    	}
    	BigInteger ans;
    	for(ans=BigInteger.ONE;;ans=ans.add(BigInteger.ONE)){
    		if(ans.multiply(cnt).compareTo(sum)>0)
    			break;
    	}
    	return ans.subtract(BigInteger.ONE).toString();
    }
}
2269
7ms