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 Mr. He was very interested in.

The vendor set up a cloth with an N*N grid drawn on it, with some squares hanging balloons and some squares without balloons.

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 there is no balloon in that square, 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 and can hit the target every time. He wants you to help him calculate how much money he is expected to spend to finish the current game.

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 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 cases 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:

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 doomed!

Note that the input represents squares without balloons

I and hqx have been fooled for a long time.

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;
}