BuringStraw

Balloon Shooting Game#

Description#

Mr. He went to Ciqikou for a weekend trip. There was a vendor on the street organizing a balloon shooting game, which caught Mr. He's interest.

The vendor set up a cloth with an N*N grid, some of the squares had balloons hanging on them, while others did not.

The rules of the game are as follows:

Step 1. Observe. If there is at least one square in each row without a balloon, and at least one square in each column without a balloon, the game ends. Otherwise, proceed to step 2.

Step 2. Roll the dice. The vendor takes out a special dice with N faces, numbered from 1 to N. The player rolls the dice twice, with the first roll resulting in the number x, and the second roll resulting in the number y (note: the numbers rolled are random).

Step 3. Shoot the balloon. If there is a balloon in the square with coordinates (x, y), the player must shoot it down. Each bullet costs 1 yuan.

If the square does not have a balloon, ignore it and the player does not need to shoot, but the player still needs to pay the vendor 1 yuan.

Step 4. Continue. Go back to step 1.

Mr. He is a sharpshooter, he can hit the target every time. He wants you to help him calculate how much money he is expected to spend to finish the game given the current setup.

Input#

The first line contains two integers N and M, where N represents the size of the grid, and M represents the number of squares without balloons at the start of the game. The next M lines each contain two integers x and y, representing the coordinates (x, y) of the squares without balloons.

Output#

One line containing a real number, the expected cost to complete the game, rounded to 2 decimal places.

Sample Input 1#

5 2 
2 3 
4 1

Sample Output 1#

11.77

For more examples, please visit wyx's blog

Approach#

This vendor is really tricky!

Let f[i][j] represent the expected cost to eliminate i rows and j columns.

There are four possible scenarios when selecting coordinates:

1. Does not affect the number of rows and columns eliminated.
2. Increases the number of rows eliminated by 1.
3. Increases the number of columns eliminated by 1.
4. Increases the number of rows and columns eliminated by 1.

The corresponding expectations are:

1. $f(i,j)\cdot \frac{(n-i)\cdot (n-j)}{n^2}$
2. $f(i,j-1)\cdot \frac{(n-i)\cdot j}{n^2}$
3. $f(i-1,j)\cdot \frac{i\cdot (n-j)}{n^2}$
4. $f(i-1,j-1)\cdot \frac{ij}{n^2}$

Therefore,

Boundary conditions:

f[0][0]=0;
for(int i=1;i<=n;++i){
	f[0][i]=f[0][i-1]+1.0*n/i;
	f[i][0]=f[i-1][0]+1.0*n/i;
}

I'm going to die!

Note that the input represents squares without balloons

I and hqx have been tricked for a long time, sob

Code#

#include<cstdio> 
#include<iostream>
using namespace std;

const int MAXN=2000+5;

int hang[MAXN],lie[MAXN];
double f[MAXN][MAXN];



int main(){
	int n,m;
	scanf("%d%d",&n,&m);
	for(int i=1;i<=m;++i){
		int x,y;
		scanf("%d%d",&x,&y);
		hang[x]=1;
		lie[y]=1;
	}
	int h=n,l=n;
	for(int i=1;i<=n;++i){
		if(hang[i])--h;
		if(lie[i])--l;
	}
	f[0][0]=0;
	for(int i=1;i<=n;++i){
		f[0][i]=f[0][i-1]+1.0*n/i;
		f[i][0]=f[i-1][0]+1.0*n/i;
	}
	for(int i=1;i<=h;++i){
		for(int j=1;j<=l;++j){
//			f[i][j]=f[i-1][j]*1.0*i*(n-j)/n/n+f[i][j-1]*1.0*(n-i)*j/n/n+f[i-1][j-1]*1.0*i*j/n/n+f[i][j]*1.0*(n-i)*(n-j)/n/n+1;
			f[i][j]=1.0*(f[i-1][j]*i*(n-j)+f[i][j-1]*(n-i)*j+f[i-1][j-1]*i*j+n*n)/(n*n-(n-i)*(n-j));
		}
	}
	printf("%.2lf\n",f[h][l]);
	return 0;
}