In the event of technical difficulties with Szkopuł, please contact us via email at szkopul@fri.edu.pl.
If you would like to talk about tasks, solutions or technical problems, please visit our Discord servers. They are moderated by the community, but members of the support team are also active there.
W grze Tetris dwuwymiarowe klocki spadają pionowo w dół na platformę. Dany klocek spada, dopóki nie napotka na przeszkodę w postaci innego klocka bądź samej platformy - wtedy zatrzymuje się i pozostaje na tej pozycji do końca gry. W tym zadaniu dla uproszczenia pomijamy znikanie całkowicie wypełnionych rzędów, które występuje w standardowej wersji gry. Ponadto załóżmy, że klocki mają wyłącznie postać poziomych pasków o krótszym (pionowym) boku długości jeden i że nie możemy manipulować w locie spadającym paskiem (obracać ani przesuwać).
Jedyne, co możemy zrobić, to wybrać kolejność spadania pasków. Twoim zadaniem jest, znając rozmiary wszystkich pasków oraz tory ich lotu, takie dobranie kolejności ich spadania, aby figura utworzona w wyniku ich spadnięcia była jak najniższa.
Napisz program który:
W pierwszym wierszu wejścia znajduje się jedna liczba całkowita (), oznaczająca liczbę pasków, które spadną na platformę. Kolejnych wierszy zawiera po dwie liczby całkowite i (), oddzielone pojedynczym odstępem i oznaczające odpowiednio długość -tego paska i jego przesunięcie w poziomie względem początku platformy.
W pierwszym wierszu wyjścia powinna znajdować się jedna liczba całkowita, oznaczająca najmniejszą możliwą wysokość figury powstałej po spadnięciu wszystkich pasków w pewnej kolejności. Kolejnych wierszy powinno zawierać opis przykładowej kolejności spadania klocków, realizującej to minimum. W -szym wierszu wyjścia powinna znajdować się jedna liczba całkowita, oznaczająca numer paska, który powinien spaść jako -ty. Paski numerujemy liczbami od 1 do w kolejności ich występowania na wejściu.
Jeżeli istnieje więcej niż jedna poprawna kolejność realizująca minimum wysokości, Twój program powinien wypisać którąkolwiek z nich.
Dla danych wejściowych:
5 4 2 3 1 3 3 4 6 4 5
poprawną odpowiedzią jest:
3 1 4 5 2 3
Autor zadania: Jakub Radoszewski.