Fişierul intrare/ieşire:	pavare.in, pavare.out	Sursă	info-arena 1.0
Autor	Mircea Bogdan Pasoi	Adăugată de
Timp execuţie pe test	0.25 sec	Limită de memorie	65536 kbytes
Scorul tău	N/A	Dificultate	3/5

Vezi solutiile trimise | Statistici

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!

Cerinta

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

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.

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.

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

Exemplu

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

Cum se trimit solutii?