Polish version    English version  
  Historia OI -> XIII OI 2005/2006


 Aktualności
 O olimpiadzie
 Komitety
 XVIII OI 2010/2011
 Historia OI
XVII OI 2009/2010
XVI OI 2008/2009
XV OI 2007/2008
XIV OI 2006/2007
XIII OI 2005/2006
Terminarz
Zadania
Wyniki III etapu
Wyniki II etapu
Wyniki I etapu
II Etap
III Etap
Przepisy
Dla zawodników
Przydatne zasoby
XII OI 2004/2005
XI OI 2003/2004
X OI 2002/2003
IX OI 2001/2002
VIII OI 2000/2001
VII OI 1999/2000
VI OI 1998/1999
V OI 1997/1998
IV OI 1996/1997
III OI 1995/1996
II OI 1994/1995
I OI 1993/1994
 Książeczki OI
 Reprezentacja
 Obozy Olimpiady
 Galeria zdjęć
 Ciekawe odsyłacze
 OIG LiveCD
 IV OIG 2009/2010
 Historia OIG
 SIO
 MAIN

Zadanie: Tetris 3D


Dostępna pamięc: 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 środku 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 D, S i N ( 1$ \le$% WIDTH=16 HEIGHT=30 N$ \le$% WIDTH=16 HEIGHT=30 20 000, 1$ \le$% WIDTH=16 HEIGHT=30 D, S$ \le$% WIDTH=16 HEIGHT=30 1 000), 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 N wierszach występują opisy kolejnych klocków, po jednym w wierszu.

Każdy opis klocka składa się z pięciu liczb całkowitych: d, s, w, x oraz y (1$ \le$% WIDTH=16 HEIGHT=30 d, 0$ \le$% WIDTH=16 HEIGHT=30 x, d + x$ \le$% WIDTH=16 HEIGHT=30 D, 1$ \le$% WIDTH=16 HEIGHT=30 s, 0$ \le$% WIDTH=16 HEIGHT=30 y, s + y$ \le$% WIDTH=16 HEIGHT=30 S, 1$ \le$% WIDTH=16 HEIGHT=30 w$ \le$% WIDTH=16 HEIGHT=30 100 000), reprezentujących klocek o długości d szerokości s i wysokości w Klocek ten będzie opadał na platformę ścianą o wymiarach d×s, 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: (x, y), (x + d, y), (x, y + s) i (x + d, y + s).

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





Wersja do druku