Din cauza blestemelor dușmanilor, asupra plantației de ‘noledge a vrăjitorului Arpsod s-a năpustit o ploaie de…meteoriți. Plantația vrăjitorului e foarte bine delimitată: aceasta are forma unei matrice cu N linii și M coloane, iar în fiecare celulă era plantat câte un fir de ‘noledge. Din motive clare de răzbunare, dușmanii nu s-au mulțumit cu o singură ploaie, astfel, pe plantația vrăjitorului au căzut meteoriți în mai multe reprize. La fiecare repriză, pe fiecare celulă a unui dreptunghi bine delimitat, au căzut exact C meteoriți. După ce ploaia s-a oprit, pe fiecare celulă se afla un “bloc” de piatră de înălțime egală cu numărul meteoriților căzuți în acea celulă. Arpsod, foarte furios, a luat următoarea decizie: va construi un laborator exact peste meteoriții căzuți, de unde își va pedepsi dușmanii. El a hotărât că cel mai bun amplasament pentru acest laborator este la înălțime maximă. Totodată, el își dorește ca laboratorul lui să aibă o suprafață cât mai mare.
Cerința
Deoarece Arpsod şi arhitectul său, Ierdnac, sunt prea ocupaţi să pregătească schița viitorului laborator, vă roagă pe voi să determinați aria maximă a unei suprafețe cu celule învecinate, de înălțime maximă precum și numărul de fire de ‘noledge rămase neatinse după căderea meteoriților ( poate au ratat vreunu’ ! ).
Date de intrare
Pe prima linie a fișierului meteoriti.in se află trei numere naturale separate prin spațiu: N și M, reprezentând dimensiunile plantației și R, reprezentând numărul de reprize de meteoriți. Pe următoarele R linii se vor afla cinci valori separate prin spațiu: r1 c1 r2 c2 C, unde r1 c1 reprezintă coordonatele colțului stânga sus ( linie coloană ) iar r2 c2 coordonatele colțului dreapta jos ( linie coloană ) ale dreptiunghiului pe care vor cădea meteoriți iar C reprezintă numărul de meteoriți ce vor cădea pe fiecare celulă din cele delimitate.
Date de ieșire
În fișierul meteoriti.out se va scrie, pe o singură linie, separate prin spațiu, aria maximă a unei suprafețe de înălțime maximă, formată numai din celule vecine respectiv numărul de fire de ‘noledge neafectate de meteoriți.
Restricții și precizări
4 ≤ N, M ≤ 2.0001 ≤ R ≤ 100.0001 ≤ r1 ≤ r2 ≤ N1 ≤ c1 ≤ c2 ≤ M1 ≤ C ≤ 20.000- Două celule se consideră vecine dacă au cel puțin o latură comună.
- Înălțimea inițială a celulelor se consideră
0. - Se garantează că pentru
30%din teste4 ≤ N, M ≤ 300și1 ≤ R ≤ 300 - Pentru rezolvarea corectă a primei cerinţe se acordă
80%din punctajul pe testul respectiv iar pentru rezolvarea corectă a celei de-a doua cerinţe se acordă20%din punctajul pe testul respectiv - Fișierul de ieșire TREBUIE să conțină exact DOUĂ valori chiar dacă doriți să rezolvați o singură cerință din cele două
- Dacă îi veți da răspunsul corect vrăjitorului, acesta vă va primi și pe voi prin laboratorul său.
- NU este bine să îl supărați pe vrăjitor!
Exemplu
meteoriti.in
5 6 7 2 2 4 3 1 4 4 4 6 2 1 5 4 6 1 2 5 3 6 1 2 3 4 3 1 5 1 5 3 3 4 2 4 2 1
meteoriti.out
3 12
Explicație
Matricea după meteoriţi:
0 0 0 0 1 1
0 1 2 0 2 2
0 1 2 0 2 2
0 2 2 2 3 3
3 3 3 0 0 0
Înălțimea maximă este 3 iar aria maximă a unei suprafețe de înălțime 3 este tot 3
Cum e corect?
cout < "As la info";
cout << "As la info";
cout >> "As la info";
Felicitări! Poți mai mult?
Avem sute de probleme pentru tine, fiecare cu explicații ușor de înțeles.
Greșit, dar nu-i bai!
Antrenează-te cu sutele de probleme pe care ți le-am pregătit. Îți explicăm fiecare problemă în parte.
Rezolvare
Iată rezolvarea de 100 de puncte pentru problema Meteoriti:
/* Implementare: Cristi Dospra
Punctaj: 100p
Utilizat: Mars + Fill(cu coada) + fstream
Complexitate: O( N*M + R )
*/
#include <fstream>
#include <algorithm>
#include <queue>
using namespace std;
#define Nmax 2002
ifstream fin ( "meteoriti.in" );
ofstream fout ( "meteoriti.out" );
int Mars[Nmax][Nmax], Nr, N, M, R;
bool viz[Nmax][Nmax];
const int dir[4][2] = { { -1,0 }, { 0,1 }, { 1,0 }, { 0,-1 } };
queue < pair < int , int > > Q;
bool Inside ( int x, int y ){
if ( x > 0 && x <= N && y > 0 && y <= M )
return 1;
return 0;
}
void Fill ( int x, int y, int h ){
Q.push ( make_pair(x,y) );
viz[x][y] = 1;
while ( !Q.empty() ){
int x = Q.front().first;
int y = Q.front().second;
Nr++;
Q.pop();
for ( int i = 0; i < 4; ++i ){
int xx = x + dir[i][0];
int yy = y + dir[i][1];
if ( Inside ( xx, yy ) && !viz[xx][yy] && Mars[xx][yy] == h ){
Q.push ( make_pair(xx, yy) );
viz[xx][yy] = 1;
}
}
}
}
int main(){
fin >> N >> M >> R;
int x1, y1, x2, y2, c;
while ( R-- ){
fin >> x1 >> y1 >> x2 >> y2 >> c;
Mars[x1][y1] += c;
Mars[x2+1][y1] -= c;
Mars[x1][y2+1] -= c;
Mars[x2+1][y2+1] += c;
}
for ( int i = 1; i <= N; ++i )
for ( int j = 1; j <= M; ++j )
Mars[i][j] += Mars[i-1][j] + Mars[i][j-1] - Mars[i-1][j-1];
int MaxArea = -1, MaxHeight = -1, UnTouched = 0;
for ( int i = 1; i <= N; ++i ){
for ( int j = 1; j <= M; ++j ){
if ( !viz[i][j] ){
Nr = 0;
Fill ( i, j, Mars[i][j] );
if ( Mars[i][j] == 0 )
UnTouched += Nr;
else{
if ( Mars[i][j] > MaxHeight ){
MaxHeight = Mars[i][j];
MaxArea = Nr;
}
else if ( Mars[i][j] == MaxHeight && Nr > MaxArea )
MaxArea = Nr;
}
}
}
}
fout << MaxArea << " " << UnTouched;
return 0;
}
Atenție
Enunțurile afișate pe această pagină aparțin exclusiv site-ului PbInfo. Astfel, pentru ștergerea conținutului, puteți să ne contactați la adresa 
.
Rezolvarea problemei #1461 Meteoriti
Pe această pagină găsești rezolvarea de 100 de puncte pentru problema #1461 Meteoriti de pe PbInfo.ro. Atenție: nu încurajăm copiatul codului! Totuși, credem cu tărie că analizarea unei soluții corecte este o metodă foarte ușoară de a învăța informatică, astfel că oferim sursele pentru peste 1500 de probleme de pe platforma PbInfo.ro.
Pentru rezolvări PbInfo de la peste 1500 de probleme, vă invităm să intrați pe site-ul nostru!