Tetris 3D
Limit pamięci: 128 MB
Autorzy gry Tetris postanowili stworzyć nową, trójwymiarową wersję gry,
w której prostopadłościenne klocki będą opadać na prostokątną platformę.
Podobnie jak w przypadku zwykłej, dwuwymiarowej wersji gry,
klocki mają opadać osobno, w pewnej ustalonej kolejności.
Dany klocek opada, dopóki nie natrafi na przeszkodę
w postaci platformy albo innego, już stojącego klocka, a wtedy się
zatrzymuje (w pozycji, w jakiej opadał) i pozostaje na swoim miejscu
do końca gry.
Autorzy nowej gry postanowili jednak zmienić charakter gry,
ze zręcznościowej na grę logiczną.
Znając kolejność opadania klocków na płaszczyznę i tory ich lotu,
gracz będzie
musiał podać wysokość najwyżej położonego punktu w układzie powstałym
po opadnięciu wszystkich klocków.
Wszystkie klocki opadają pionowo w dół i nie obracają się w
trakcie opadania.
Dla ułatwienia wprowadźmy na platformie
układ współrzędnych kartezjańskich o początku w jednym z jej
narożników i osiach równoległych do jej boków.
Napisz program, który zautomatyzuje
sprawdzanie, czy gracz udzielił poprawnej odpowiedzi.
Zadanie
Napisz program, który:
-
wczyta ze standardowego wejścia opisy kolejno opadających
klocków,
-
wyznaczy najwyższy punkt układu klocków po zakończeniu
ich opadania,
-
wypisze wynik na standardowe wyjście.
Wejście
W pierwszym wierszu wejścia znajdują się trzy liczby całkowite
, i
(, ),
oddzielone pojedynczymi odstępami i oznaczające odpowiednio:
długość i szerokość platformy oraz liczbę klocków, które na
nią opadną.
W następnych wierszach występują opisy kolejnych klocków, po
jednym w wierszu.
Każdy opis klocka składa się z pięciu liczb całkowitych:
, , , oraz
(, , ,
, , ,
),
reprezentujących klocek o długości
szerokości i wysokości .
Klocek ten będzie opadał na platformę ścianą o wymiarach ,
przy czym długość i szerokość klocka będą równoległe odpowiednio
do długości i szerokości platformy.
Wierzchołki rzutu klocka na platformę będą miały współrzędne:
, , i .
Wyjście
Pierwszy i jedyny wiersz wyjścia powinien zawierać dokładnie jedną liczbę
całkowitą, oznaczającą wysokość najwyższego punktu w układzie klocków
po zakończeniu ich opadania.
Przykład
Dla danych wejściowych:
7 5 4
4 3 2 0 0
3 3 1 3 0
7 1 2 0 3
2 3 3 2 2
poprawną odpowiedzią jest:
6
Autor zadania: Jakub Radoszewski.