import java.io.IOException;

public class Main {

	static int n;
	static double [][]source=new double[9][9];
	static double [][]sum=new double[9][9];
	static double [][][][][] buffer;
	static double xp;
	static double MIN=0.00000001;
	
	static double all(int nn,int sx,int sy,int ex,int ey){
		if(buffer[nn][sx][sy][ex][ey]!=Double.MIN_VALUE)
			return buffer[nn][sx][sy][ex][ey];
		
		if(nn==1){
			buffer[nn][sx][sy][ex][ey] = sum[ex][ey] + sum[sx-1][sy-1] - sum[ex][sy-1] - sum[sx-1][ey]
			                            - xp;
			buffer[nn][sx][sy][ex][ey]*=buffer[nn][sx][sy][ex][ey];
			return buffer[nn][sx][sy][ex][ey];
		}
		if(sx==ex&&sy==ey || sx>ex || sy>ey){
			return -1.0;
		}
		double min=Double.MAX_VALUE;
		
		for(int i=sx;i<ex;i++){
			double a1=all(nn-1,  sx, sy,i ,ey);
			double a2=all(1,     i+1,sy,ex,ey);
			if(a1>=-MIN&&a2>=-MIN)
				min=Math.min(min, a1+a2);


			double b1=all(1,     sx, sy,i ,ey);
			double b2=all(nn-1,  i+1,sy,ex,ey);
			if(b1>=-MIN&&b2>=-MIN)
				min=Math.min(min, b1+b2);
		}
		
		for(int j=sy;j<ey;j++){
			double a1=all(nn-1,  sx, sy, ex ,j) ;
			double a2=all(1,     sx, j+1,ex,ey);
			if(a1>=-MIN&&a2>=-MIN)
				min=Math.min(min, a1+a2);

			double b1=all(nn,    sx, sy, ex ,j);
			double b2=all(nn-1,  sx, j+1,ex,ey);
			if(b1>=-MIN&&b2>=-MIN)
				min=Math.min(min, b1+b2);
		}
		if(min==Double.MAX_VALUE){
			min=-1.0;
			return min;
		}
		buffer[nn][sx][sy][ex][ey] = min;
		return min;
	}
	
	public static void main(String[] args) {

			n=nextInt();
			
			buffer=new double[n+1][9][9][9][9];
			for(int i=0;i<=n;i++)
				for(int j=0;j<9;j++)
					for(int k=0;k<9;k++)
						for(int l=0;l<9;l++)
							for(int m=0;m<9;m++)
								buffer[i][j][k][l][m]=Double.MIN_VALUE;
			
			for(int i=1;i<=8;i++){
				int lineSum=0;
				for(int j=1;j<=8;j++){
					source[i][j]=nextInt();
					lineSum+=source[i][j];
					sum[i][j]=sum[i-1][j]+lineSum;
				}
			}
			xp=sum[8][8]*1.0/(n*1.0);
			double result = Math.sqrt(all(n,1,1,8,8)*1.0/(n*1.0));
			result = ((int)(result * 1000.0 + 0.5)) * 1.0 /1000.0;
			//System.out.println(result);
			System.out.printf("%.3f\n",result);
			
	}
	

	final static int nextInt(){
		int v = 0;
		char t = 0;
		boolean neg=false;
		try {
			while (!Character.isDigit(t = (char) System.in.read()) && t!='-')
				;
			if(t=='-'){
				neg=true;
				t='0';
			}
			do {
				v *= 10;
				v += t - '0';
			} while (Character.isDigit(t = (char) System.in.read()));
		} catch (IOException e) {
		}
		return neg?-v:v;
	}

}

• zhong yu AAC (314) lin_ 2006-08-17 22:00:07
  • Re:zhong yu AAC (11) 20053565 2007-08-18 06:28:47
• zhong yu AC le (314) lin_ 2006-08-17 22:00:10