Pavare

pavare

==Include(page="template/taskheader" task_id="pavare")==

== include(page="template/taskheader" task_id="pavare") ==

Gigel, primar in orasul sau, s-a gandit sa renoveze strada principala, strada de dimensiuni $N*M$ compusa din bucati de dimensiuni $1*1$. Majoritatea bucatilor sunt stricate, dar mai exista $K$ bucati care sunt considerate bune. Dorind sa plateasca cat mai putini bani, Gigel a luat de la un negustor blocuri de dimensiuni $2*2$ la pretul unui bloc de dimensiuni $1*1$. Pentru a pava strada trebuie sa amplaseze cat mai multe din aceste blocuri pe bucati stricate, fara sa paveze vreo bucata buna deoarece ar aparea denivelari, si fara sa se suprapuna blocurile $2*2$. El si-a dat seama ca mai bine ar fi cumparat blocuri $1*1$, pentru ca ar fi acoperit toata strada fara batai de cap, dar acum nu mai are de ales si are nevoie de ajutorul tau!

Poveste ...

h2. Cerinta

Determinati numarul maxim de blocuri $2*2$ pe care le poate pune primarul pentru a repara strada.

...

h2. Date de Intrare

h2. Restrictii

Pe prima linie din fisierul $pavare.in$ se vor afla trei numere intregi separate prin cate un spatiu: $N, M$ si $K$. Pe urmatoarele $K$ linii se vor afla perechi de numere intregi reprezentand linia si coloana pe care se afla o bucata buna.

...

h2. Date de Iesire

h2. Date de intrare

Pe prima linie in fisierul $pavare.out$ se va afla un numar natural reprezentand numarul maxim de blocuri $2*2$ care pot fi amplasate pe strada.

...

h2. Restrictii si precizari

h2. Date de iesire

* $1 ≤ N ≤ 150$
* $1 ≤ M ≤ 15$
* $1 ≤ K ≤ N*M$
* Liinile sunt numerotate de la $1$ la $N$, iar coloanele de la $1$ la $M$

...

h2. Exemplu

table(example). |_. pavare.in |_. pavare.out |
| 4 6 3
1 1
2 6
3 3 | 4 |
 
h3. Explicatie
 
Acesta este un amplasament posibil al blocurilor:
!problema/pavare?untitled.gif!
 
==Include(page="template/taskfooter" task_id="pavare")==
 

| pavare.in | pavare.out |
| linia1
linia2
linia3
| linia1
linia2
|
== include(page="template/taskfooter" task_id="pavare") ==

46