Fişierul intrare/ieşire:pavare.in, pavare.outSursăinfo-arena 1.0
AutorMircea Bogdan PasoiAdăugată de
Timp execuţie pe test0.25 secLimită de memorie65536 kbytes
Scorul tăuN/ADificultatenormalnormalnormalnormalnormal

Vezi solutiile trimise | Statistici

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!

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

pavare.inpavare.out
4 6 3
1 1
2 6
3 3
4

Explicatie

Acesta este un amplasament posibil al blocurilor:

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content