2019 JUST Programming Contest |
---|
Finished |
You are given a grid $$$g$$$ consisting of $$$n$$$ rows each of which is divided into $$$m$$$ columns. The grid contains unique values between $$$1$$$ and $$$n \times m$$$ (inclusive).
Also, you are given two values $$$h$$$ and $$$w$$$, and your task is to find the smallest median value that can be found in a rectangle of size $$$h \times w$$$.
A rectangle of size $$$h \times w$$$ is a rectangle consisting of $$$h$$$ rows and $$$w$$$ columns such that its top left corner is at a cell ($$$a,\,b$$$) and its right bottom corner is at a cell ($$$c,\,d$$$), and the following conditions are satisfied: ($$$c - a + 1 \equiv h$$$) and ($$$d - b + 1 \equiv w$$$).
The median of a set of numbers is the middle element in the sorted list of the given set. For example, the median of $$$\{2, 1, 3\}$$$ is $$$2$$$ and the median of $$$\{4, 2, 3, 1, 5\}$$$ is $$$3$$$.
The first line contains four integers $$$n$$$, $$$m$$$, $$$h$$$, and $$$w$$$ ($$$1 \le n,\,m \le 10^3$$$, $$$1 \le h,\,w \le n$$$), in which $$$n$$$ and $$$m$$$ are the number of rows and columns in the grid, respectively, and $$$h$$$ and $$$w$$$ are representing the size of the required rectangle. Both $$$h$$$ and $$$w$$$ are odd integers.
Then $$$n$$$ lines follow, each line contains $$$n$$$ integers, giving the grid. It is guaranteed that the grid contains unique values between $$$1$$$ and $$$n \times m$$$ (inclusive).
Print a single line containing the smallest median value that can be found in a rectangle of size $$$h \times w$$$.
4 4 3 3 13 16 15 4 5 2 8 9 14 11 12 10 1 6 3 7
6
In the first test case, there are $$$4$$$ possible rectangles of size $$$3 \times 3$$$, which are:
So, the smallest median value that can be found in a rectangle of size $$$3 \times 3$$$ is $$$6$$$.
Name |
---|