În fiecare oră, norii se deplasează cu câte o poziție în direcția de deplasare, iar atunci când norul părăsește în totalitate suprafața continentului, intră din nou pe continent deasupra aceleași țări acoperite la prima intrare (poziția inițială) și continuă deplasarea. Norii intră pentru prima dată deasupra continentului după un timp de așteptare *W* și se pot suprapune în timpul deplasării. Un nor se numește ”întreg”, dacă în timpul deplasării, există cel puțin o oră în care norul este situat deasupra continentului și nu depășește marginile continentului.
În exemplul din _figura 2_ sunt trei nori, simbolizați prin cifrele *1*, *2* și *3*. Norul *1* – de tip *1* - pătrunde pe continent prin țara ([*2*],[*1*]) după 3 ore de așteptare, norul *2* – de tip *3* - pătrunde prin țara ([*4*],[*1*]) după *0* ore de așteptare, iar norul *3* – de tip *5* - pătrunde prin țara ([*1*],[*3*]) după *1* oră de așteptare. În acest exemplu este redată poziția fiecărui nor în primele *9* ore. În țările care nu sunt acoperite de nori cerul este senin, iar în țările peste care se suprapun cel puțin doi nori este furtună.
În exemplul din _figura 2_ sunt trei nori, simbolizați prin cifrele *1*, *2* și *3*. Norul *1* – de tip *1* - pătrunde pe continent prin țara (*2*,*1*)după 3 ore de așteptare, norul *2* – de tip *3* - pătrunde prin țara (*4*,*1*) după *0* ore de așteptare, iar norul *3* – de tip *5* - pătrunde prin țara (*1*,*3*) după *1* oră de așteptare. În acest exemplu este redată poziția fiecărui nor în primele *9* ore. În țările care nu sunt acoperite de nori cerul este senin, iar în țările peste care se suprapun cel puțin doi nori este furtună.
!problema/nori?nori-2.png!
!problema/nori?nori-2.ppm!
h2. Cerințe
Cunoscând numerele naturale *R*, *C*, *N*, coordonatele țării pe unde intră fiecare nor pe continent, tipul acestuia, precum și timpul de așteptare al fiecărui nor la prima intrare pe continent, se cere:
# Să se determine numărul *A* al norilor întregi și timpul *B* minim după care toți norii întregi sunt situați deasupra continentului, fără a depăși marginile acestuia;
# Cunoscând și un timp *T*, să se determine numărul *S* de țări care au cerul senin după *T* ore și numărul *F* de țări în care este furtună după *T* ore.
h2. Date de intrare
Fișierul de intrare $nori.in$ conține:
* Pe prima linie, un număr natural *P* care poate avea doar valorile *1* sau *2*;
* Pe linia a doua, patru numere naturale *R*, *C*, *N* și *T*, în această ordine, despărțite prin câte un spațiu, cu semnificația din enunț;
* Pe următoarele *N* linii se află câte patru numere naturale *X[~i~]*, *Y[~i~]*, *Z[~i~]* și *W[~i~]*, unde [*i*] ∈ {*1*, *2*, *3*, …, *N*} în această ordine, despărțite prin câte un spațiu. Numerele *X[~i~]* și *Y[~i~]* reprezintă linia și coloana, țării prin care intră norul *i* pe continent, *Z[~i~]* reprezintă tipul norului *i*, iar *W[~i~]* reprezintă timpul de așteptare al norului *i* la prima intrare deasupra continentului.
Fișierul de intrare $nori.in$ ...
h2. Date de ieșire
* Dacă valoarea lui *P* este *1*, se va rezolva numai cerința *1*. În acest caz, fișierul de ieșire $nori.out$ va conține pe prima linie două numere naturale *A* și *B*, în această ordine, despărțite prin câte un spațiu. Numărul *A* reprezintă numărul norilor întregi, iar *B* este timpul minim determinat;
* Dacă valoarea lui *P* este *2*, se va rezolva numai cerința *2*. În acest caz, fișierul de ieșire $nori.out$ va conține pe prima linie două numere naturale *S* și *F*, în această ordine, despărțite printr-un spațiu. Numărul *S* reprezintă numărul de țări care au cer senin după *T* ore, iar *F* reprezintă numărul de țări în care este furtună după *T* ore.
În fișierul de ieșire $nori.out$ ...
h2. Restricții
* *2* ≤ *R*, *C* ≤ *200*; *1* ≤ *N* ≤ *50*; *1* ≤ *T* ≤ *2 000 000*;
* *1* ≤ *Z[~i~]* ≤ *25*; *Z[~i~]* este număr impar; *Z[~i~]* poate fi mai mare decât *R* sau *C*;
* *0* ≤ *W[~i~]* ≤ *200*;
* Pentru cerinta *1*, se garantează că *1* ≤ *B* < *300 000*;
* Pot exista mai mulți nori care intră pe continent prin aceeași țară;
* Niciun nor nu intră pe continent prin țara cu coordonatele ([*1*],[*1*]);
* Dacă *X[~i~]* = *1* atunci *2* ≤ *Y[~i~]* ≤ *C*
* Dacă *Y[~i~]* = *1* atunci *2* ≤ *X[~i~]* ≤ *R*
* Pentru rezolvarea corectă a cerinței *1* se obține [*30%*] din punctaj, iar pentru cerința *2* se obține [*70%*] din punctaj.
h2. Exemple
table(example).
|_. nori.in |_. nori.out |_. Explicație |
| 1
5 3 3 9
2 1 1 3
4 1 3 0
1 3 5 1
| 2 9
| Vezi exemplul din figura 2. Sunt 2 nori întregi și anume norul 1 și norul 2.
Cei doi nori sunt situați în întregime deasupra continentului, prima dată după 9 ore.
|
| 2
5 3 3 9
2 1 1 3
4 1 3 0
1 3 5 1
| 8 2
| Vezi exemplul din figura 2. După T=9 ore țările cu cer senin sunt la coordonatele:
(1, 1), (1, 2), (1, 3), (2, 1), (2, 3), (3, 1), (3, 3), (5, 1) iar țările în care
este furtună sunt la coordonatele: (4, 3) și (5, 2).
|
* $... ≤ ... ≤ ...$
h2. Exemplu
table(example).
|_. nori.in |_. nori.out |
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
|
h3. Explicație
...
== include(page="template/taskfooter" task_id="nori") ==
