This page is still under construction.

Parts of this page are still being built. What you see may change.

Wizard Shark and the Tornado

Time limit1sMemory limit512 MB

Summary
Simulate a tornado sweeping from the grid center outward in a spiral to (1,1), scattering each cell's sand at fixed ratios with truncation, and total the sand blown off the grid.
Level

Medium7 of 10

Topics
Simulation, Implementation, Array, Matrix
Solved
No attempts yet

Problem

Wizard Shark has learned the tornado, and today he wants to practice it on a sand field divided into an N×N grid. Position (r, c) means row r, column c of the grid, and A[r][c] is the amount of sand at (r, c).

When the tornado is cast, it starts moving from the center cell of the grid. The tornado moves one cell at a time. The following is the movement of the tornado when N = 7.

Each time the tornado moves one cell, the sand scatters at fixed ratios as follows.

When the tornado moves from x to y, all the sand at y moves to the cells marked with ratios and to the cell marked α. The amount of sand that moves to a cell marked with a ratio is that ratio of the sand at y, and the fractional part is discarded in the calculation. The amount of sand that moves to α equals the remaining sand that did not move to the cells marked with ratios. When sand moves to a cell that already has sand, the amounts are added. The figure above is for the tornado moving left, and for movement in other directions, the figure is rotated to that direction.

The tornado moves until it reaches (1, 1) and then disappears. Sand can move outside the grid. Find the amount of sand that has gone outside the grid when the tornado disappears.

Input

The first line gives the size of the grid, N. From the second line, N lines give the sand in each cell of the grid. The integer given at the c-th position of the r-th line is A[r][c].

Output

Print the amount of sand that has gone outside the grid.

Constraints

  • 3 ≤ N ≤ 499
  • N is odd
  • 0 ≤ A[r][c] ≤ 1,000
  • The amount of sand in the center cell is 0

Examples5

  1. Example 1

    Input
    5
0 0 0 0 0
0 0 0 0 0
0 10 0 0 0
0 0 0 0 0
0 0 0 0 0
    Expected output
    10

  2. Example 2

    Input
    5
0 0 0 0 0
0 0 0 0 0
0 100 0 0 0
0 0 0 0 0
0 0 0 0 0
    Expected output
    85

  3. Example 3

    Input
    7
1 2 3 4 5 6 7
1 2 3 4 5 6 7
1 2 3 4 5 6 7
1 2 3 0 5 6 7
1 2 3 4 5 6 7
1 2 3 4 5 6 7
1 2 3 4 5 6 7
    Expected output
    139

  4. Example 4

    Input
    5
100 200 300 400 200
300 243 432 334 555
999 111 0 999 333
888 777 222 333 900
100 200 300 400 500
    Expected output
    7501

  5. Example 5

    Input
    5
0 0 100 0 0
0 0 100 0 0
0 0 0 0 0
0 0 100 0 0
0 0 100 0 0
    Expected output
    283