Solved by 246 users: ...
UserDateAttemptTimeCMSC
fetetriste`19 dec 2007`C++400.03271
kia`15 jul 2006`C++300.02291
Madiyar_Tktl`15 dec 2007`C++800.04300
Madiyar_Tktl`15 dec 2007`C++100.04307
Madiyar_Tktl`15 dec 2007`C++600.04310
Romka`10 jul 2009`C++100.01327
dragonghy`14 apr 2007`FPC200.01334
tnndye`22 may 2007`FPC100.02334
Philip_PV`01 aug 2008`C500.23337
Philip_PV`01 aug 2008`C++600.08339
Philip_PV`01 aug 2008`C++200.07345
FaLLeNs`11 oct 2006`C++200.01347
Philip_PV`01 aug 2008`C++100.06349
LoLitter`17 oct 2007`C++100.02353
AsukaNoKaze`06 jun 2006`C++200.03353
 C++ 147 FPC 67 Kylix 16 C 10 Java 8 Python 1 Perl 1
` >  >  >  >  >  >  >  >  >  > `

2x1-paving

Time limit = 5 second(s)

Memory limit = 8 Mb

We have square paper N x N. Some cells are black, others are white. Domino-tile is piece of size 2 x 1. The problem is to place maximum number of domino-tiles (pave maximum area) at the paper so that tiles do not overlap and cover only white cells.

Input The first line contains N, 2 ≤ N ≤ 20, Then N lines follow with chars '#' and '.' Char '#' corresponds to black cell, '.' corresponds to white cell.

Output Maximum number of domino-tiles.

 Input#1```2 ## #. ``` Output#1```0 ```
 Input#2```2 .. .. ``` Output#2```2 ```
 Input#3```3 ... ... ..# ``` Output#3```4 ```
 Input#4```4 .... .##. .##. .... ``` Output#4```6 ```

Author:
Barsky Eugene & Voroztsov Artem, IV MIPT Contest
11 April 2004

<PREV | Problem set | Search related messages | NEXT>

 © acm.mipt DevGroupThe page was generated in 220ms