Test generated by the following program is hard for recursive solutions on some languages. For example Java recursive solution uses approx 31M of stack on this test while the whole ML of this problem is 16M.

Very very strange that the test set does not contain test with maximal possible answer.

const
   height = 1000;
   width = 1000;
var
   line, column : integer;
begin
   writeln(height, ' ', width);
   for line := 1 to height do begin
      for column := 1 to width do begin
         if
            (line = 1) or (line = height) or
            (column = 1) or (column = width) or
            (line mod 4 = 1) and (column > 2) or
            (line mod 4 = 3) and (column < width - 1)
         then begin
            write('#');
         end
         else begin
            write('.');
         end;
      end;
      writeln;
   end;
end.

Edited by author 09.01.2009 17:29

up

Answer 498500

Edited by author 17.03.2011 03:31

Some tests with n ≠ m were added. 113 authors lost AC.