sahara

Sahara

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

Undeva, în deşertul Sahara, ilustrul biolog Sahraa Gaea a conceput şi construit un sistem de irigaţii ingenios, sistem cu care îşi propune să irige o zonă deşertică dreptunghiulară bogată în nutrienţi minerali. Zona deşertică este împărţită în N×M pătrate de latură unitate. În fiecare pătrat se află un dispozitiv de picurare ce asigură o anumită cantitate de apă în funcţie de comanda primită de la centrul de control al sistemului.

Undeva, în deşertul Sahara, ilustrul biolog Sahraa Gaea a conceput şi construit un sistem de irigaţii ingenios, sistem cu care îşi propune să irige o zonă deşertică dreptunghiulară bogată în nutrienţi minerali. Zona deşertică este împărţită în $N × M$ pătrate de latură unitate. În fiecare pătrat se află un dispozitiv de picurare ce asigură o anumită cantitate de apă în funcţie de comanda primită de la centrul de control al sistemului.

Sistemul de irigare este astfel conceput încât să irige (ude), pe baza unor comenzi automatizate, parcele dreptunghiulare ale regiunii deşertice.

Orice parcelă are laturile paralele cu laturile zonei deşertice şi este identificată prin coordonatele colţurilor stânga-sus (x1,y1), respectiv dreapta-jos (x2,y2).  La fiecare comandă se specifică parcela care va fi udată şi cantitatea de apă (exprimată în litri) cu care va fi irigat fiecare pătrat al acesteia.
Un pătrat al zonei deşertice devine fertil dacă acumulează cel puţin Q litri de apă.

Orice parcelă are laturile paralele cu laturile zonei deşertice şi este identificată prin coordonatele colţurilor stânga-sus $(x1,y1)$, respectiv dreapta-jos $(x2,y2)$. La fiecare comandă se specifică parcela care va fi udată şi cantitatea de apă (exprimată în litri) cu care va fi irigat fiecare pătrat al acesteia.
Un pătrat al zonei deşertice devine fertil dacă acumulează cel puţin $Q$ litri de apă.

h2. Cerinţă

h2. Date de intrare

Fişierul de intrare $sahara.in$ conţine pe prima linie trei numere naturale N M Q despărţite prin câte un spaţiu, cu semnificaţia din enunţ.
Pe cea de-a doua linie a fişierului se găseşte un număr natural T. Pe fiecare dintre următoarele T linii se află descrierea parcelelor udate sub forma: x1 y1 x2 y2 q , adică cinci numere naturale despărţite prin spaţiu, unde  x1 y1 x2 y2 reprezintă coordonatele colţurilor stânga-sus, respectiv dreapta-jos ale parcelei,  q  cantitatea de apă cu care va fi irigat fiecare pătrat al parcelei.

Fişierul de intrare $sahara.in$ conţine pe prima linie trei numere naturale $N$ $M$ $Q$ despărţite prin câte un spaţiu, cu semnificaţia din enunţ.
Pe cea de-a doua linie a fişierului se găseşte un număr natural $T$. Pe fiecare dintre următoarele $T$ linii se află descrierea parcelelor udate sub forma: $x1 y1 x2 y2 q$, adică cinci numere naturale despărţite prin spaţiu, unde $x1 y1 x2 y2$ reprezintă coordonatele colţurilor stânga-sus, respectiv dreapta-jos ale parcelei, $q$ cantitatea de apă cu care va fi irigat fiecare pătrat al parcelei.

h2. Date de ieşire

* $1 ≤ q ≤ 1000$
* $1 ≤ Q ≤ 10000$
* $1 ≤ T ≤ 50000$

* Iniţial zona deşertică nu conţine ”apă”;
* Pot exista suprafaţe conexe fertile formate dintr-un singur pătrat fertil;
* Parcelele se pot suprapune.

* Iniţial zona deşertică nu conţine ”apă”
* Pot exista suprafaţe conexe fertile formate dintr-un singur pătrat fertil
* Parcelele se pot suprapune

h2. Exemplu

h3. Explicaţie
Cantitatea de apă acumulată în solul regiunii este:

  1 4 4 1 1 1 0
  1 4 7 4 4 4 3
  1 4 7 4 4 4 3
  0 5 8 5 5 5 5
  4 6 6 2 4 4 2
  4 4 4 3 5 5 3
  0 0 0 3 5 5 3
  0 0 0 3 3 3 3
Aria maximă a unei suprafeţe fertile este egală cu 10. Suprafaţa se consideră fertilă dacă acumulează cel puţin 5 litri de apă.

  $1 4 4 1 1 1 0$
  $1 4 7 4 4 4 3$
  $1 4 7 4 4 4 3$
  $0 5 8 5 5 5 5$
  $4 6 6 2 4 4 2$
  $4 4 4 3 5 5 3$
  $0 0 0 3 5 5 3$
  $0 0 0 3 3 3 3$
Aria maximă a unei suprafeţe fertile este egală cu $10$. Suprafaţa se consideră fertilă dacă acumulează cel puţin $5$ litri de apă.

== include(page="template/taskfooter" task_id="sahara") ==