Fișierul intrare/ieșire	balon.in, balon.out	Sursă	ONI 2023 clasa a 6-a
Autor	Florentina Ungureanu	Adăugată de	Cristian Frâncu • francu
Timp de execuție pe test	0.75 sec	Limită de memorie	65536 KB
Scorul tău	N/A	Dificultate	2.5

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

Vezi soluțiile trimise | Statistici

Balon (clasa a 6-a)

Notă: această problemă este o aplicație “de manual” a ultracunoscutului “șmen al lui Mars”, o noțiune ce nu a apărut niciodată la clasa a șasea. Problema nu se rezolvă cu șmenul lui Mars, ea este însăși șmenul lui Mars. Desigur că o problemă ce cere exact manualul nu are ce căuta la faza națională a unei olimpiade. De ce comisia a decis să o dea este un mister. Cu reticență am adăugat-o pe acest site, pentru completitudine – din nefericire a fost dată la ONI clasa a șasea în 2023.

Firma TgM produce plăci de umflat baloane. O placă de dimensiuni n x m este formată din n linii cu câte m celule pătrate de latură 1, fiecare celulă conținând un dispozitiv de care poate fi prins un balon pentru a fi umflat. Un balon are un nivel de umplere b_ij cuprins între 1 (dezumflat) și nivelul de umplere maxim posibil k. Introducerea unui nou volum de aer într-un balon umplut la nivelul maxim k, conduce la spargerea lui (nivel k + 1). Fiecare balon spart este înlocuit automat cu un balon nou aflat la nivelul de umplere 1 înainte de a introduce un nou volum de aer în oricare dintre baloanele de pe placă.

Introducerea aerului în anumite baloane se face printr-o acționare care constă în următorii pași:

• se conectează un sistem cilindru-piston la dispozitivul dintr-o celulă aflată pe linia x și coloana y;
• se selectează o valoare naturală nenulă d;
• se apasă butonul Air aflat pe mânerul pistonului.

În urma acționării butonului Air, fiecare balon situat în pătratul cu colțul din stânga sus (x, y) cu latura d trece de la nivelul de umplere curent la nivelul de umplere imediat următor. Dacă pătratul de latură d depășește una sau mai multe din marginile plăcii, se transmite aer doar în baloanele aflate în interiorul acestuia. La acționarea butonului se consumă un număr de unități de volum de aer egal cu numărul de baloane aflate în interiorul pătratului.

Cerințe

Dându-se dimensiunile unei plăci n și m, nivelul maxim posibil de umplere a unui balon k, numărul p de acționări ale butonului Air, nivelul inițial de umplere al fiecărui balon de pe placă și pentru fiecare dintre acționările pistonului cele trei valori x, y și d corespunzătoare, scrieți un program care determină și afișează:

1. numărul de unități de aer consumate după cele p acționări ale butonului Air;
2. numărul de baloane sparte după cele p acționări ale butonului Air;
3. nivelul maxim de umplere a unui balon după cele p acționări ale butonului Air și numărul de baloane aflate la acest nivel de umplere.

Date de intrare

Fișierul de intrare balon.in conține pe prima linie un număr natural C, reprezentând cerința ce trebuie rezolvată (1, 2 sau 3), pe a doua linie patru numere naturale nenule n, m, k și p, cu semnificația din enunț, pe fiecare din următoarele n linii câte m valori reprezentând nivelul inițial de umplere a baloanelor de pe linia respectivă, iar pe fiecare din ultimele p linii câte trei numere naturale x, y și d corespunzătoare unei acționări a pistonului. Numerele aflate pe aceeași linie a fișierului sunt separate prin câte un spațiu.

Date de ieșire

În fișierul de ieșire balon.out:

• dacă C = 1, se va afișa pe prima linie numărul de unități de aer consumate după cele p acționări ale butonului Air;
• dacă C = 2, se va afișa pe prima linie numărul de baloane sparte după cele p acționări ale butonului Air;
• dacă C = 3, se vor afișa pe prima linie două numere separate printr-un spațiu reprezentând nivelul maxim de umplere a unui balon după cele p acționări ale butonului Air și numărul de baloane aflate la acest nivel de umplere.

Restricții

• C ∈ {1, 2, 3};
• 1 ≤ n, m, d ≤ 1 000;
• 1 ≤ x ≤ n și 1 ≤ y ≤ m;
• 3 ≤ k, p ≤ 1 000 000;
• 1 ≤ b_ij ≤ k, pentru oricare 1 ≤ i ≤ n și 1 ≤ j ≤ m;

Exemple