Fișierul intrare/ieșire	parking.in, parking.out	Sursă	OJI 2024 clasa a 7-a
Autor	Florentina Ungureanu	Adăugată de	Cristian Frâncu • francu
Timp de execuție pe test	0.17 sec	Limită de memorie	65536 KB
Scorul tău	N/A	Dificultate	3.25

Poți vedea testele pentru această problemă accesând atașamentele .

Vezi soluțiile trimise | Statistici

Parking (clasa a 7-a)

Mark a construit o parcare dreptunghiulară, pe care a împărțit-o, utilizând marcaje, în locuri de parcare pătrate, organizate pe n linii (numerotate de la 1 la n) și m coloane (numerotate de la 1 la m). Astfel, un loc de parcare poate fi identificat prin numărul liniei și numărul coloanei pe care acesta se află. Orice mașină poate fi parcată în interiorul unui loc de parcare, paralel cu liniile orizontale de marcaj sau paralel cu liniile verticale, fără a depăși conturul pătratului corespunzător. Mark a construit un zid de împrejmuire a parcării, întrerupt în dreptul unor locuri de parcare, pentru a permite ieșirea mașinilor din parcare. Considerăm că zidul este plasat pe linia 0 (nord), coloana 0 (vest), linia n + 1 (sud) și coloana m + 1 (est).

O mașină parcată paralel cu marcajele orizontale se poate deplasa pe linie, spre stânga sau spre
dreapta, putând ieși din parcare dacă ajunge la o întrerupere a zidului de la vest sau de la est, și doar dacă nu există o nicio altă mașină parcată în sensul ei de deplasare către ieșire. O mașină parcată paralel cu marcajele verticale se poate deplasa pe coloană în sus sau în jos, putând ieși din parcare dacă ajunge la o întrerupere a zidului de la nord sau de la sud și doar dacă nu există nicio altă mașină parcată în sensul ei de deplasare către ieșire. Mașinile se pot deplasa mergând în față sau în marșarier. De exemplu, mașina parcată în locul (2,2) paralel cu marcajele orizontale nu poate ieși din parcare, deoarece dacă se deplasează spre vest ajunge la zid, iar dacă se deplasează spre est, nu poate ajunge la întreruperea din zid corespunzătoare acelei linii din cauza altor mașini parcate pe traseu, dar mașina din locul (2,6) poate ieși deplasându-se spre est. Ieșirea din parcare se face în serii consecutive, mașinile dintr-o serie începând deplasarea simultan (după ce au ieșit toate mașinile din seria anterioară); din seria curentă fac parte toate mașinile care, exact la acel moment, au drumul liber spre cel puțin o întrerupere de zid (nu este necesară mișcarea niciunei alte mașini rămase în parcare, inclusiv a celor din seria curentă), chiar dacă traseul lor către ieșire se intersectează cu traseul altor mașini din aceeași serie, aflate în deplasare. În prima serie ies toate mașinile care pot pleca din parcare imediat, fără a fi condiționate de mutarea sau părăsirea parcării de către alte mașini.

Cerințe

Scrieți un program care, cunoscând dimensiunile parcării, pozițiile întreruperilor din zid, numărul de mașini, iar pentru fiecare mașină numărul liniei și al coloanei corespunzătoare locului în care este parcată și modul de parcare a acesteia, rezolvă următoarele două cerințe:

1. determină numărul de mașini care pot ieși din parcare fără a fi condiționate de mutarea sau de părăsirea parcării de către alte mașini (numărul de mașini care pot ieși în prima serie);

1. determină numărul total mașini care pot ieși din parcare, precum și numărul de serii în care se realizează ieșirea tuturor acestor mașini.

h2 Date de intrare

Fișierul de intrare parking.in conține pe prima linie numerele naturale c, n, m, k și q reprezentând, în ordine, numărul cerinței, numărul de linii și numărul de coloane ale parcării, numărul de întreruperi ale zidului parcării, respectiv, numărul de mașini parcate. Pe următoarele k linii se află câte două numere naturale i și j reprezentând pozițiile (linia, respectiv coloana) întreruperilor din zidul parcării. Pe următoarele q linii se află câte trei numere naturale x, y și p reprezentând, în ordine, numărul liniei și al coloanei corespunzătoare locului în care este parcată o mașină și modul de parcare a acesteia (p = 0 pentru parcare paralelă cu marcajele orizontale, respectiv p = 1 pentru parcare paralelă cu marcajele verticale). Valorile scrise pe aceeași linie sunt separate prin câte un spațiu.

Date de ieșire

Fișierul de ieșire parking.out va conține o singură linie pe care va fi scris:

• numărul de mașini care au ieșit din parcare în prima serie, dacă c = 1;
• numărul total de mașini care au ieșit din parcare și numărul de serii în care s-a realizat ieșirea mașinilor, separate printr-un spațiu, dacă c = 2.

Restricții

• 2 ≤ n, m ≤ 1 000
• 2 ≤ k ≤ 2 · n + 2 · m
• 2 ≤ q ≤ min ( n · m, 100 000)
• 1 ≤ i ≤ n, pentru j = 0 sau j = m + 1 și 1 ≤ j ≤ m, pentru i = 0 sau i = n + 1
• 1 ≤ x ≤ n, 1 ≤ y ≤ m, 0 ≤ p ≤ 1
• Se garantează pentru datele de test că numărul de serii obținute va fi cel mult 10 000, dacă c = 2.
• Pe parcursul deplasării pentru a ieși din parcare mașinile vor circula astfel încât nu se vor ciocni.

Exemple