| Fişierul intrare/ieşire: | amat.in, amat.out | Sursă | ONI 2019, clasa a 9-a, ziua 1 |
| Autor | Eugen Nodea | Adăugată de |  Alex Enache •Alex18mai |
| Timp execuţie pe test | 0.75 sec | Limită de memorie | 65536 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
Amat
Pasionat de informatică şi de puzzle-uri, Dorel a construit o matrice A de dimensiunea N×M lipind mai multe piese dreptunghiulare de diferite dimensiuni. Fiecare piesă este compusă din elemente de dimensiunea 1×1 şi reţin o aceeaşi valoare (vezi exemplele). Matricea rezultată nu are spaţii libere, iar piesele din care este compusă nu se suprapun. Nu există două piese cu aceeaşi valoare.
Deşi iniţial părea că acest design este unul inedit, nu a durat mult până când Dorel s-a plictisit. Astfel, acum el doreşte să ”upgradeze” matricea construită. Dorel alege o submatrice delimitată de coordonatele (x1,y1) –colţul stânga-sus, (x2,y2) –colţul dreapta-jos (1≤x1≤x2≤N, 1≤y1≤y2≤M) , unde creşte toate valorile elementelor submatricei cu valoarea V.
Dorel efectuează în ordine Q operaţii de upgrade, operaţii numerotate de la 1 la Q. La finalizarea celor Q operaţii de upgrade, toate elementele din matrice au valoarea mai mare sau egală cu K. După o operaţie de upgrade, structura iniţială a matricei se modifică.
Cerinţe
Cum priceperea lui Dorel este proverbială, trebuie să îl ajutaţi în rezolvarea următoarelor cerinţe:
- determinarea coordonatelor piesei cu număr maxim de elemente înainte ca Dorel să efectueze operaţiile de upgrade;
- determinarea numărului minim de operaţii de upgrade după care toate elementele matricei au valoarea mai mare sau egală cu K.
Date de intrare
Datele de intrare se citesc din fişierul amat.in, care are următoarea structură:
- pe prima linie se află numărul natural C, care poate fi egal cu 1 sau 2, în funcţie de cerinţa ce trebuie rezolvată;
- pe linia următoare se află două numerele naturale N şi M cu semnificaţia din enunţ;
- pe următoarele N linii se găsesc elementele matricei A.
- dacă C = 2 atunci fişierul de intrare mai conţine:
- pe linia N+2 numerele naturale Q K cu semnificaţiile din enunţ;
- pe următoarele Q linii descrierea submatricelor asupra cărora se efectuează operaţii de upgrade de forma: x1 y1 ×2 y2 V
Date de ieşire
Datele de ieşire se vor scrie în fişierul amat.out, astfel:
Dacă C = 1 se vor scrie, separate prin spaţiu patru numere naturale nenule x1 y1 ×2 y2 ce reprezintă coordonatele colţului stânga-sus, respectiv colţului dreapta-jos unde este plasată piesa cu număr maxim de elemente înainte de upgrade. Dacă există mai multe astfel de piese, atunci vor fi scrise coordonatele piesei pentru care coordonatele colţului stânga-sus are valoarea liniei cea mai mare, iar la linii egale, se va alege piesa cu coordonata coloanei cea mai mare.
Dacă C = 2 se va scrie numărul natural nenul NR ce reprezintă numărului minim de operaţii de upgrade după care toate elementele matricei au valoarea mai mare sau egală cu K.
Restricţii
- 2 ≤ N, M ≤ 1000; 1 ≤ Q ≤ 100000; 1 ≤ V ≤ 1000
- -1000 ≤ elementele matricei A înainte de upgrade ≤ 1000
- Operaţiile de upgrade se efectuează obligatoriu în ordinea citirii
- Pentru teste în valoare de 30 de puncte, C = 1
- Pentru teste în valoare de 30 de puncte, C = 2 şi N, M, Q ≤ 250
- Pentru teste în valoare de 50 de puncte, C = 2 şi Q ≤ 4000
- Pentru teste în valoare de 70 de puncte, C = 2.
Exemplu
| amat.in | amat.out | Explicaţie |
|---|---|---|
| 1 4 6 1 1 1 3 2 2 1 1 1 3 2 2 6 4 4 4 2 2 6 4 4 4 5 7 | 3 2 4 4 | Se rezolvă cerinţa 1. Matricea iniţială construită de Dorel este: 1 1 1 3 2 2 1 1 1 3 2 2 6 4 4 4 2 2 6 4 4 4 5 7 Există 3 piese cu număr maxim de valori egale, dar piesa care corespunde cerinţelor are coordonatele: 3 2 4 4 . |
| 2 4 6 1 1 1 3 2 2 1 1 1 3 2 2 6 4 4 4 2 2 6 4 4 4 5 7 3 6 1 1 3 3 5 1 2 4 6 5 4 1 4 3 1 | 2 | Se rezolvă cerinţa 2. Matricea iniţială construită este cea prezentată mai sus. Dorel efectuează 3 operaţii de upgrade. Matricea obţinută după efectuarea primului upgrade: 6 6 6 3 2 2 6 6 6 3 2 2 11 9 9 4 2 2 6 4 4 4 5 7 Matricea obţinută după efectuarea celui de-al doilea upgrade: 6 11 11 8 7 7 6 11 11 8 7 7 11 14 14 9 7 7 6 9 9 9 10 12 Matricea obţinută după efectuarea celui de-al treilea upgrade: 6 11 11 8 7 7 6 11 11 8 7 7 11 14 14 9 7 7 7 10 10 9 10 12 La final tuturor operaţiilor de upgrade, matricea are toate valorile mai mari sau egale 6. Se observă că sunt suficiente primele două operaţii de upgrade pentru că toate elementele matricei să fie mai mari sau egale cu 6. |
