Informatica Online Judge

  Tractor [0729 / 02D9]

Time Limit(Test case) : 1000(ms)
Number of users who solved : 78   Total Tried : 131


The Champion of this Problem (C++) : gs16109 - ms / 1020byte
My Best Submission (C++) : N/A

[]

Background

농부 존의 농장은 넓기도 하지만 땅이 고르지 않다. 영역별로 높이가 달라서 일반적인 트랙터로는 모든 땅을 다 관리하기 어렵다.

따라서 이번에 새로 개발된 트랙터를 사려고 한다. 새로 개발된 트랙터는 상, 하, 좌, 우로 이동할 수 있으며 고도차가 D이하일 경우에는 땅을 개간하는데 무리가 없다고 한다.

농부 존의 농장은 N*N(N은 500이하의 자연수)의 영역으로 구성되고, 각 영역의 고도가 음이 아닌 정수로 주어진다. 영역의 고도차 D를 극복할 수 있는 트랙터의 가격은 D달러이다.

농부 존의 농장의 각 영역별 높이가 주어질 때,농장의 반 이상을 개간할 수 있는 가장 싼 트랙터를 살 수 있도록 프로그램을 작성하시오.

(단, 농장의 셀의 수가 홀수일 때는 반올림한 셀의 수만큼 개간할 수 있어야 한다.)

Input

첫 번째 줄에는 농장의 크기 N이 주어진다.
다음 줄부터 N줄에 걸쳐서 N개의 영역별 높이가 공백으로 구분되어 주어진다.

각 지점의 높이는 최대 1,000,000이다.

Output

농장의 반 이상을 개간할 수 있는 가장 싼 가격의 트랙터의 가격을 출력한다.

IO Example

입력1
5
0 0 0 3 3
0 0 0 0 3
0 9 9 3 3
9 9 9 3 3
9 9 9 9 3

출력1
3

설명)
트랙터 가격 3이면 높이가 3이하인 모든 영역을 관리할 수 있다. 농장의 높이가 0인영역과 3인 영역을 모두 개간할 수 있으므로 반 이상 관리할 수 있다.

입력2
3
3 4 5
0 0 7
3 4 5

출력2
2

Submit : [C/C++] | [C++11] | [Obj-C] | [Java] | [Python]
Prob Analysis : [Problem Statistics] | [Solution]