J5. Square Pool
레이팅 미적용의견: 0
Ron wants to build a square pool in his square \(N\)-by-\(N\) yard, but his yard contains \(T\) trees. Your job is to determine the
side length of the largest square pool he can build.
\(T < N^2\)
Marks
The following table shows how the available 15 marks are
distributed.
| Marks Awarded | Length/Width of Yard | Number of Trees |
|---|---|---|
| 3 marks | \(N \leq 50\) | \(T=1\) |
| 5 marks | \(N \leq 50\) | \(T \leq 10\) |
| 4 marks | \(N \leq 500\,000\) | \(T \leq 10\) |
| 3 marks | \(N \leq 500\,000\) | \(T \leq 100\) |
The first line of input will be an integer \(N\) with \(N\geq2\). The second line will be the
positive integer \(T\) where \(T < N^2\). The remaining input will be
\(T\) lines, each representing the
location of a single tree. The location is given by two positive
integers, \(R\) and then \(C\), separated by a single space. Each tree
is located at row \(R\) and column
\(C\) where rows are numbered from top
to bottom from \(1\) to \(N\) and columns are numbered from left to
right from \(1\) to \(N\). No two trees are at the same
location.
Output one line containing \(M\)
which is the largest positive integer such that some \(M\)-by-\(M\) square contained entirely in Ron’s yard
does not contain any of the \(T\)
trees.
5
1
2 43A picture of the yard is below. The location of the tree is marked
by
and one of several (3)-by-(3) squares that do not contain the tree is highlighted. All larger squares contain a tree.
15
8
4 7
4 1
14 11
10 6
13 4
4 10
10 3
9 147A picture of the yard is below. The location of each tree is marked
by
and one of several (7)-by-(7) squares that do not contain a tree is highlighted. All larger squares contain a tree.
평가 및 의견
J5. Square Pool
Log in to rate problems.
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
J5. Square Pool