FXTZ II

Target: If the noob's HP is less than the master's, the noob will lose. Calculate the possiblity that noob wins.

Main Idea:

Assume there are n snowballs, so the damages are 2^0, 2^1,..., 2^(N-1). Let P_n be the possiblity of noob winning in the n snowballs game. Note that Pn also means the prossiblity that the noob has less damage than the master within n snowballs of different damages, that is to say, at this time the noob won't die.

We can see that the 2^(N-1) snowball decides who win in the n snowball game, so we need to throw it to the master. Another point is that we need to make sure that the master always has more damage than the noob.

So,

when the 2^(N-1) snowball is the 1st snowball, we throw it to the master => (1/2)*P₀ , P₀ == 1

when the 2^(N-1) snowball is the 2nd snowball, we throw it to the master => (1/2)*P₁,

    P₁ means the first ball should make sure the noob has less damage

when the 2^(N-1) snowball is the 3rd snowball, we throw it to the master => (1/2)*P₂

    P₂ means the first two balls should make sure the noob has less damage

...

when the 2^(N-1) snowball is the nth snowball, we throw it to the master => (1/2)*P_n-1

Besides, in each case we need to pick the first m balls from all n balls and pick the 2^(N-1) ball from the rest, so [(n-m)/n)] * [1/(n-m)] is the possiblity of picking the 2^(N-1) ball and placing it after the first m balls.

Finally, we can get the equation:

P_n = P₀ * (1/2) * [(n-0)/n] * [1/n] + P₁ * (1/2) * [(n-1)/n] * [1/(n-1)] + ... + P_n-1 * (1/2) * [(1)/n] * [1/1]

P_n-1 = P₀ * (1/2) * [(n-1-0)/(n-1)] * [1/(n-1)] + P₁ * (1/2) * [(n-1-1)/(n-1)] * [1/(n-1-1)] + ... + P_n-2 * (1/2) * [1/(n-1)] * [1/1]

Then we can get the recursion formula:

P_n = (2*n-1)/(2*n)/P_n-1

This is the code written by another one using JAVA BigInteger

http://blog.csdn.net/tju_virus/article/details/7860170

import java.math.BigInteger;
import java.util.Scanner;

public class HDOJ_1212 {
	public static void main(String[] str) {
		Integer num;
		BigInteger tmp;
		BigInteger[] fenzi = new BigInteger[505];
		BigInteger[] fenmu = new BigInteger[505];
		Scanner cin = new Scanner(System.in);
		int k, n;
		fenzi[0] = new BigInteger("1");
		fenmu[0] = new BigInteger("1");
		for (int i = 1; i <= 500; i++) {
			num = 2 * i - 1;
			tmp = new BigInteger(num.toString());
			fenzi[i] = fenzi[i - 1].multiply(tmp);
			num = 2 * i;
			tmp = new BigInteger(num.toString());
			fenmu[i] = fenmu[i - 1].multiply(tmp);
			tmp = gcd(fenzi[i], fenmu[i]);
			fenzi[i] = fenzi[i].divide(tmp);
			fenmu[i] = fenmu[i].divide(tmp);
		}
		while (cin.hasNext()) {
			k = cin.nextInt();
			for (int i = 0; i < k; i++) {
				n = cin.nextInt();
				System.out.println(fenzi[n].toString() + "/"
						+ fenmu[n].toString());
			}
		}
	}

	public static BigInteger gcd(BigInteger a, BigInteger b) {
		if (b.equals(new BigInteger("0")))
			return a;
		else
			return gcd(b, a.mod(b));
	}
}