Problema tetris1
Problema tetris1 a fost dată la ONI 2013 clasa a 6a.
Este o problemă de simulare, ce ne cere să așezăm piese pătrate într-un pahar, similar cu jocul tetris. Ea are o rezolvare brută destul de accesibilă, ce se dovedește a fi și cea cerută.
Într-o rezolvare directă, brută, este destul de clar că vom menține un vector ce memorează pentru fiecare coloană înălțimea la care s-a ajuns pe acea coloană. Când așezăm o piesă verificăm mai întâi că este între pereții stânga-dreapta ai paharului, apoi calculăm maximul coloanelor de sub ea. Dacă putem așeza piesa, respectiv acel maxim plus latura piesei nu depășesc înălțimea paharului, atunci o așezăm, actualizând înălțimile tuturor coloanelor de sub ea la înălțimea maximă calculată la care se adaugă latura piesei.
Iată o implementare posibilă:
#include <stdio.h>
int h[1000];
int main() {
FILE *fin, *fout;
int n, m; // nr linii, nr coloane
int gata, lat, colp, c, maxh, maxl, len;
fin = fopen( "tetris1.in", "r" );
fscanf( fin, "%d%d", &n, &m );
colp = lat = maxh = gata = 0;
while ( colp + lat <= m // piesa anterioara a incaput la dreapta?
&& maxh + lat <= n // piesa anterioara a incaput pe inaltime?
&& fscanf( fin, "%d%d", &lat, &colp ) == 2 ) { // avem piesa?
colp--; // ajustam pentru numerotare de la zero a coloanelor
// incercam plasarea piesei
if ( colp + lat <= m ) { // incape la dreapta?
maxh = h[colp];
c = colp + 1;
while ( maxh + lat <= n && c < colp + lat ) {
if ( h[c] > maxh )
maxh = h[c];
c++;
}
if ( maxh + lat <= n ) // asezam piesa
for ( c = colp; c < colp + lat; c++ )
h[c] = maxh + lat;
}
}
fclose( fin );
maxh = -1;
for ( c = 0; c < m; c++ ) {
if ( h[c] > maxh ) {
maxh = h[c];
maxl = len = 1;
} else if ( h[c] == maxh ) {
len++;
if ( len > maxl )
maxl = len;
} else
len = 0;
}
fout = fopen( "tetris1.out", "w" );
fprintf( fout, "%d\n%d\n", maxh, maxl );
fclose( fout );
return 0;
}Ce complexitate are această soluție?
Fiecare piesă necesită O(L) calcule, unde L este latura ei, deoarece va parcurge acele coloane atât pentru găsirea maximului cât și pentru actualizarea înălțimilor. Avem maxim P piese, deci complexitatea algoritmului este O(P·L). Înlocuind obținem circa un miliard de operații, care pare cam mult pentru a se încadra în timp.
În realitate nu este așa, deoarece înălțimea paharului este limitată la 1000. Deoarece piesele nu se pot suprapune pentru fiecare piesă vom efectua radical din aria sa operații, aria paharului fiind limitată la un milion. Cazul cel mai rău este când toate piesele au latură 1, caz în care vom face un milion de operații, iar timpul este, de fapt, dominat de citire.
Să ținem cont de faptul că timpul este pe măsură de mare, iar memoria folosită este foarte mică, 4KB, ceea ce înseamnă că încape în cache, programul executându-se mai rapid.