Indian National Olympiad in Informatics

Online Programming Contest, 10-11 September 2005

IARCS home > OLYMPIAD

Basic Division

Problem 1: Nikhil's Birthday Cake, (K Narayan Kumar, CMI)

It is Nikhil's birthday and he has to cut his birthday cake. It is a square cake. He has to make one horizontal and one vertical cut to divide the cake into four pieces. Then, his sister, his father and his mother get to choose their pieces. Finally, he gets the last piece left on the plate.

If it were a simple cake, it would be best for Nikhil to cut it into four equal quarters. However, the cake is divided into N ×N squares. Some of these squares are covered with chocolate chips. Everyone in his family loves chocolate and since everyone else gets to choose their piece before he does, he is likely to get the piece with the least number of squares covered with chocolate chips. Nikhil is more interested in the chocolate chips than the cake itself, so he would like to cut the cake in such a way that he is guaranteed to get as many squares covered with chocolate chip as possible.

He has been told that he his cuts must not pass through any of the squares (that is, the cuts must be along the boundaries of the squares).

Suppose the cake looks like:

. . # . . # . .
. # # . . # . .
. . . . . . # .
. # # . . . . .
. . # . # . . .
. . . . . . # .
. . . . . . . .
. . # . . # . .

where a # denotes a square covered with chocolate chips and a . denotes a square with no chocolate chips on it. Here are two possible ways in which Nikhil could cut the cake.

. . # . .|# . .             . . # .|. # . .     
. # # . .|# . .             . # # .|. # . .     
. . . . .|. # .             . . . .|. . # .      
. # # . .|. . .             -------|-------
---------|-----             . # # .|. . . .    
. . # . #|. . .             . . # .|# . . .
. . . . .|. # .             . . . .|. . # .
. . . . .|. . .             . . . .|. . . .
. . # . .|# . .             . . # .|. # . .

With the first set of cuts, he will end up with the bottom-right piece containing just two squares covered with chocolate chips. On the other hand, if he cuts it as indicated in the second figure then he is guaranteed to get three squares covered with chocolate chips. You can verify that this is the best he can do.

Your task is to help Nikhil determine the best way to cut the cake to maximize his share of squares covered with chocolate chips.

Input format

The first line of input contains a single integer N indicating the number of squares in each line. This is followed by N lines of input each containing N characters (each of which is either a # or a .).

Output format

The first line of the output contains a single integer M indicating the maximum number of squares covered with chocolate chips that Nikhil can get. This followed by a line containing two integers R and C, describing a way to cut the cake so that he gets M squares covered with chocolate chips. The number R indicates that the horizontal cut is placed between the Rth and (R+1)st rows of squares. The number C indicates that the vertical cut is placed between the Cth and (C+1)st column of squares. If more than one combination of R and C yield the value M, it suffices to print out any one combination.

Test data

For all inputs, N ≤ 2000. Further, you may assume that N ≤ 50 in 80% of the inputs.

Example

We now illustrate input and output formats using the example described above.

Sample input

8
..#..#..
.##..#..
......#.
.##.....
..#.#...
......#.
........
..#..#..

Sample output

3
3 4



Copyright (c) IARCS 2003-2024;   Last Updated: 10 Nov 2005