Skok w bok
Limit pamięci: 32 MB
Plansza do gry „Skok w bok” jest nieskończoną taśmą pól, nieograniczoną zarówno w lewo jak i w prawo.
Na polach planszy stoją pionki.
Ich liczba jest skończona.
Na jednym polu może stać równocześnie wiele pionków.
Zakładamy, że pierwsze od lewej pole, na którym jest przynajmniej jeden pionek, ma numer .
Pola na prawo od niego są oznaczone kolejno liczbami naturalnymi , a pola w lewo liczbami ujemnymi: .
Ustawienie pionków na taśmie, które będziemy także nazywać konfiguracją, można opisać w ten sposób, że dla każdego pola,
na którym jest co najmniej jeden pionek, podaje się numer pola i liczbę pionków na tym polu.
Są dwa rodzaje ruchów, zmieniających konfiguracje: skok w prawo i skok w lewo.
Skok w prawo polega na zabraniu po jednym pionku z wybranych dwóch sąsiednich pól o numerach oraz i dodaniu jednego pionka na polu .
Skok w lewo: zabieramy jeden pionek z pola , a dodajemy po jednym na polach i .
Mówimy, że konfiguracja jest końcowa, jeśli na dowolnych dwóch sąsiednich polach znajduje się co najwyżej jeden pionek.
Dla każdej konfiguracji istnieje dokładnie jedna konfiguracja końcowa, którą można z niej otrzymać w wyniku skończonej liczby skoków w prawo lub w lewo.
Zadanie
Ułóż program, który:
- wczytuje opis konfiguracji początkowej ze standardowego wejścia,
- znajduje konfigurację końcową, do jakiej można doprowadzić daną konfigurację początkową i zapisuje wynik na standardowe wyjście.
Wejście
W pierwszym wierszu standardowego wejścia jest zapisana jedna liczba całkowita dodatnia .
Jest to liczba niepustych pól danej konfiguracji początkowej, .
W każdym z kolejnych wierszy znajduje się opis jednego niepustego pola konfiguracji początkowej w postaci pary liczb całkowitych oddzielonych odstępem.
Pierwsza liczba to numer pola, a druga — to liczba pionków na tym polu.
Te opisy są uporządkowane rosnąco według numerów pól.
Największy numer pola nie przekracza , a liczba pionków na żadnym polu nie przekracza .
Wyjście
W pierwszym wierszu standardowego wyjścia należy zapisać konfigurację końcową,
do której można przekształcić daną konfigurację początkową — numery kolejnych niepustych pól konfiguracji końcowej.
Numery te powinny być uporządkowane rosnąco.
Liczby w wierszu powinny być pooddzielane pojedynczym odstępem.
Przykład
Dla danych wejściowych:
2
0 5
3 3
poprawną odpowiedzią jest:
-4 -1 1 3 5
Autor zadania: Bogdan S. Chlebus.