== include(page="template/taskheader" task_id="pavare") ==
==Include(page="template/taskheader" task_id="pavare")==
Poveste ...
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!
h2. Cerinta
...
Determinati numarul maxim de blocuri $2*2$ pe care le poate pune primarul pentru a repara strada.
h2. Restrictii
h2. Date de Intrare
...
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 intrare
h2. Date de Iesire
...
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. Date de iesire
h2. Restrictii si precizari
...
* $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
| pavare.in | pavare.out |
| linia1
linia2
linia3
| linia1
linia2
|
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")==
== include(page="template/taskfooter" task_id="pavare") ==
