Blockout este versiunea in 3
dimensiuni a jocului tetris. Astfel, piese avand forme
diferite trebuiesc plasate intr-un paralelipiped de o anumita inaltime. In aceasta problema, va trebui sa simulati o varianta
simplificata a acestui joc.
Consideram un paralelipiped cu baza
de dimensiuni NxN si inaltime infinita. In interiorul acestuia, cad succesiv
piese ce se vor aseza pe pozitia cea mai joasa posibila. Piesa
inainteaza pe axa verticala cate o unitate si se opreste atunci cand, fie a atins baza paralelipipedului (inaltime 0), fie se sprijina
pe o piesa precedenta.
Piesele considerate vor avea deasemenea forma
paralelipipedica iar pozitia lor in planul orizontal va
fi data.
Cerinta
Pentru fiecare piesa se cere sa
afisati inaltimea finala la care se va opri baza piesei.
Date de intrare
Prima linie a fisierului blockout.in va contine doua numere intregi N si M separate printr-un singur spatiu. N reprezinta
dimensiunea bazei paralelipipedului, iar M numarul de piese. Urmatoarele
M linii vor contine cate 5 intregi ce corespund unei
piese x1 y1 x2 y2 h; primii doi intregi reprezinta
coordonatele coltului stanga-sus al bazei piesei, urmatorii doi coordonatele
coltului dreapta-jos al bazei piesei si ultimul reprezinta inaltimea piesei.
Date de iesire
Pentru fiecare piesa se va scrie pe
o linie in fisierul blockout.out inaltimea finala a bazei piesei.