### National Olympiad in Informatics, China, 1999

## Day 2, Problem 1 - Chessboard Division

An 8×8 chessboard is divided as follows: Cut out one rectangular section such that the remaining section is also rectangular. Continue cutting the remaining section again in this fashion. After making (`n` − 1) cuts, there should be `n` remaining rectangular sections of the chessboard. Each cut may only be made on grid-lines of the board.

The first figure above is an example of an acceptable cutting method, while the second figure above is an example of an unacceptable cutting method.

Each cell in the original chessboard has a score value, and the score value of any rectangular division is the sum of the scores of all of the cells that it contains. Now we must divide the 8×8 chessboard into `n` rectangular sections using the method above, while minimizing the *mean squared error* of the scores of each section.

The mean squared error (MSE) , where the mean , and `x _{i}` represents the score of the

`i`-th board division.

Write a program that, given the scores of cells on the chess board and the number of divisions `n`, finds the minimum possible value of σ.

### Input Format

The first line of input contains the integer `n` (1 < `n` < 15). Line 2 to line 9 of input each contain 8 non-negative space-separated integers less than 100, describing the score values of each cell on the chessboard.

### Output Format

The output should contain the single number σ, rounded and displayed to three digits after the decimal point.

## Sample Input3 1 1 1 1 1 1 1 3 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 0 3 ## Sample Output1.633 |

All Submissions

Best Solutions

**Point Value:** 15 (partial)

**Time Limit:** 1.00s

**Memory Limit:** 16M

**Added:** May 04, 2014

**Languages Allowed:**

C++03, PAS, C, HASK, ASM, RUBY, PYTH2, JAVA, PHP, SCM, CAML, PERL, C#, C++11, PYTH3

## Comments (Search)

It's quiet in here...