W razie problemów technicznych ze Szkopułem, prosimy o kontakt mailowy pod adresem [email protected].
Jeśli chciałbyś porozmawiać o zadaniach, rozwiązaniach lub problemach technicznych, zapraszamy na serwery Discord. Są one moderowane przez społeczność, ale członkowie zespołu technicznego też są tam aktywni.
Mały Jaś poznał ostatnio grę Tetris. W grze tej klocki o różnych kształtach opadają na platformę. Gra ta zainspirowała Jasia do zastanowienia się nad następującym problemem. Załóżmy że wszystkie klocki to prostokąty o wymiarach , gdzie to długość boku poziomego. 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. Mając dane wymiary, kolejność opadania i tory lotu klocków 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.
Napisz program, który:
W pierwszum wierszu wejścia znajdują się dwie liczby całkowite (), oznaczające odpowiednio: szerokość platformy oraz liczbę klocków, które na nią opadną. W następnych wierszach występują opisy kolejno opadających klocków.
Każdy opis klocka składa się z dwóch liczb całkowitych: (), reprezentujących klocek o szerokości . Wierzchołki rzutu klocka na platformę będą miały współrzędne: i .
W jedynym wierszu wyjścia należy wypisać wysokość najwyższego punktu w układzie klocków po zakończeniu ich opadania.
Dla danych wejściowych:
8 5 3 1 2 6 1 4 4 3 5 0
poprawną odpowiedzią jest:
3
Rysunek ilustruje wygląd układu klocków po zakończeniu ich opadania. Kolory kolejno opadających klocków to: zielony, żółty, czerwony, niebieski, fioletowy.