Klocki
Limit pamięci: 32 MB
Bajtazar jako małe dziecko uwielbiał bawić się klockami.
Jego zabawa polegała na układaniu z klocków kolumn o losowo wybranych
wysokościach, a następnie ich porządkowaniu.
Bajtazar wybierał liczbę , a następnie starał się w minimalnej liczbie ruchów
tak uporządkować klocki, by pewne kolejnych
kolumn klocków miało tę samą wysokość.
Pojedynczy ruch polega na:
-
położeniu jednego klocka na szczycie wybranej kolumny klocków
(Bajtazar posiadał ogromne pudło z zapasowymi klockami,
więc ten ruch jest zawsze możliwy), lub
-
zdjęciu jednego klocka ze szczytu wybranej kolumny.
Bajtazar nigdy nie był pewien czy wybrane przez niego rozwiązanie było
optymalne i poprosił Cię o napisanie programu, który pomoże
mu rozwiązywać ten problem.
Zadanie
Napisz program który:
-
wczyta ze standardowego wejścia liczbę i opis początkowego układu klocków,
-
wyznaczy rozwiązanie wymagające minimalnej liczby ruchów,
-
wypisze otrzymane rozwiązanie na standardowe wyjście.
Wejście
W pierwszym wierszu standardowego wejścia
zapisane są dwie liczby całkowite oraz
(), oddzielone pojedynczym odstępem.
W kolejnych wierszach zapisane są początkowe wysokości kolumn klocków;
wiersz -wszy zawiera jedną liczbę całkowitą
- wysokość -tej kolumny klocków,
czyli liczbę klocków z których się ona składa.
Wyjście
Na standardowe wyjście należy wypisać optymalne rozwiązanie, to jest
układ klocków, który:
-
zawiera kolejnych kolumn o tej samej wysokości,
-
można otrzymać z początkowego układu w minimalnej liczbie ruchów.
Wyjście powinno składać się z
wierszy, a każdy z nich powinien
zawierać jedną liczbę całkowitą.
W pierwszym wierszu należy wypisać minimalną liczbę ruchów, potrzebnych
do uzyskania żądanego układu.
W
-szym wierszu (dla
) należy wypisać liczbę
-
końcową wysokość
-tej kolumny klocków.
W przypadku, gdy istnieje wiele rozwiązań, należy podać dowolne z nich.
Przykład
Dla danych wejściowych:
5 3
3
9
2
3
1
poprawną odpowiedzią jest:
2
3
9
2
2
2
Autor zadania: Tomasz Waleń.