==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!
 
h2. Cerinta
 
Determinati numarul maxim de blocuri $2*2$ pe care le poate pune primarul pentru a repara strada.
 
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 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. 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
 
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/raw")==
 
Link: [1]File-List
 
Pavare
 
 
 
Gigel, primar in orasul sau, s-a gandit sa renoveze strada principala, strada de dimensiuni M*N 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. 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 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. 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 Explicatie
4 6 3 4 Acesta este un amplasament posibil al blocurilor:
 
1 1 1 2 3 4 5 6
1
2 6 2
3
3 3 4
 
 
 
References
 
Visible links
1. file:///home/eval/eval/www/infoarena/docs/arhiva/pavare/enunt.files/filelist.xml
==Include(page="template/taskfooter" task_id="pavare")==

46