HomeVolumesContestsSectionsForumsUsersPrintHelpAbout

Contests > "Informatics Stars" Online Contests - 2011-2014 > problem:


2012-11-40. 50558 - Biggest Barn

"Informatics Stars" Online Contests - 2011-2014

Start: Oct.20.2012 at 10:00:00 AM
Finish: Oct.20.2012 at 03:00:00 PM
The contest is finished!
• Contest scoreboard

Guest
• Review clarifications (1)

Contest problems

• 2012-02-8. 50596 - Your Ride Is He...
• 2012-02-8. 50596 - Your Ride Is He...
• 2012-03-01. 50563 - Long Modulus
• 2012-03-02. 50567 - Input Data No...
• 2012-03-04. 50597 - Drawing Diam...
• 2012-10-02. 50555 - Frequency of L...
• 2012-10-04. 50598 - Minimum Sum
• 2012-11-30. 50656 - Divisibility by 11
• 2012-11-40. 50558 - Biggest Barn
• 2012-12-10. 50546 - Average Fuel P...
• 2012-12-20. 50574 - Triangular Nu...
• 2012-12-30. 50684 - Sum of prime ...
• 2013-01-10. 50584 - Total invoice ...
• 2013-01-30. 50599 - Sum of Squar...
• 2013-03-20. 50578 - Mersenne prime
• 2013-03-30. 50360 - National Elections
• 2013-03-40. 50705 - Student Clubs

Feedback

If you notice incorrect translations in Contester, please let author know.

Time limit 2000/4000/4000/4000 ms. Memory limit 65000/65000/65000/65000 Kb.
USACO FALL '97.

PROBLEM 4: Big Barn [USACO FALL '97]

Farmer John wants to place a big square barn on his square farm. He hates to cut down trees on his farm and wants to find a location for his barn that enables him to build it only on land that is already clear of trees. For our purposes, his land is divided into N x N parcels. The input contains a list of parcels that contain trees. Your job is to determine and report the largest possible square barn that can be placed on his land without having to clear away trees. The barn sides must be parallel to the horizontal or vertical axis.

EXAMPLE

Consider the following grid of Farmer John's land where `.' represents a parcel with no trees and `#' represents a parcel with trees:

          1 2 3 4 5 6 7 8
        1 . . . . . . . .
        2 . # . . . # . .
        3 . . . . . . . .
        4 . . . . . . . .
        5 . . . . . . . .
        6 . . # . . . . .
        7 . . . . . . . .
        8 . . . . . . . .

The largest barn is 5 x 5 and can be placed in either of two locations in the lower right part of the grid.

INPUT FORMAT

Line 1: two integers: N (1 <= N <= 250), the number of parcels on a side, and T (1 <= T <= 600) the number of parcels with trees
Line 2..T+1: two integers (1 <= each integer <= N), the row and column of a tree parcel

SAMPLE INPUT (file INPUT.TXT):

8 3
2 2
2 6
6 3

OUTPUT FORMAT

The output file should consist of exactly one line, the maximum side length of John's barn.

SAMPLE OUTPUT (file OUTPUT.TXT):

5
Для отправки решений необходимо выполнить вход.

www.contester.ru