# -*- coding: utf-8 -*-
"""
Created on Mon Mar 12 09:55:35 2018
@author: lizihua
將一個(gè)8*8的棋盤進(jìn)行分割，將原棋盤分割下一個(gè)矩陣，同時(shí)確保剩下的棋盤也是矩陣；
再將剩下的棋盤繼續(xù)進(jìn)行如上分割，這樣割(n-1)次，最后原棋盤被分割成n塊矩形棋盤；
注意：每次分割只能沿著棋盤格子的邊進(jìn)行分割
原棋盤每個(gè)格子都有一個(gè)分值，一個(gè)矩形棋盤的總分，為所含各格分值之和；
其中，Xi為第i塊矩形棋盤的總分
對給出的棋盤和n，使得矩形棋盤總分的均方差最小，并輸出
"""
 
import numpy as np
import math
 
n=int(input("請輸入分割次數(shù)："))
#每個(gè)格子的分值
s=np.zeros((8,8))
for i in range(8):
  s[i]=input("請輸入第"+str(i)+"行各格的分值：").split(' ')
  #將line中的元素轉(zhuǎn)換為整型
  s[i] = list(map(int, s[i]))
 
zero1=np.zeros(8)
zero2=np.zeros(9)
#向s中的最上面加入一行0
s=np.insert(s,0,values=zero1,axis=0)
#向s中的第一列加入一列0
s=np.insert(s,0,values=zero2,axis=1)
res=np.ones((15,8,8,8,8))*(-1) #fun的記錄表
sums=np.zeros((9,9))       #(1,1)到(i,j)的矩形分值之和
res=np.ones((15,9,9,9,9))*(-1) #fun的記錄表
sums=np.zeros((9,9))       #(1,1)到(i,j)的矩形分值之和
for i in range(1,9):
  #rowsum是列之和，所以當(dāng)i變化時(shí)，rowsum要清零
  rowsum=0
  for j in range(1,9):
    
    rowsum+=s[i][j]
    sums[i][j]+=sums[i-1][j]+rowsum
 
print(sums)
 
#(x1,y1)到(x2,y2)的矩形分值之和
def calsum(x1,y1,x2,y2):
  return sums[x2][y2]-sums[x2][y1-1]-sums[x1-1][y2]+sums[x1-1][y1-1]
 
#定義遞歸函數(shù)fun()
def fun(n,x1,y1,x2,y2):
  #注意：MIN是局部變量，一定在函數(shù)里賦值，否則結(jié)果會(huì)有問題
  MIN=10000000
  if res[n][x1][y1][x2][y2] != -1:
    return res[n][x1][y1][x2][y2]
  if n==1:
    t=calsum(x1,y1,x2,y2)  #分割后的矩形棋盤(不再分割的那塊)的總分
    res[n][x1][y1][x2][y2]=t*t   #Xi*Xi
    return t*t
  for i in range(x1,x2):
    a=calsum(x1,y1,i,y2)
    c=calsum(i+1,y1,x2,y2)
    t=min(fun(n-1,x1,y1,i,y2)+c*c,fun(n-1,i+1,y1,x2,y2)+a*a)
    if t<MIN:
      MIN=t
    
  for j in range(y1,y2):
    a=calsum(x1,y1,x2,j)
    c=calsum(x1,j+1,x2,y2)
    t=min(fun(n-1,x1,y1,x2,j)+c*c,fun(n-1,x1,j+1,x2,y2)+a*a)
    if t<MIN:
      MIN=t
  res[n][x1][y1][x2][y2]=MIN
  return MIN
 
 
result=n*fun(n,1,1,8,8)-sums[8][8]*sums[8][8]
print(math.sqrt(result/(n*n)))