Jedynki
Limit pamięci: 128 MB
Niech będzie ciągiem zer i jedynek.
Skrajnie samotną jedynką (w skrócie SKS jedynką) w jest skrajna (ostatnia lub pierwsza) jedynka,
która dodatkowo nie sąsiaduje bezpośrednio z żadną inną jedynką.
Na przykład, w ciągu 10001010 są dwie SKS jedynki,
w ciągu 1101011000 nie ma żadnej SKS jedynki,
a w ciągu 1000 jest tylko jedna SKS jedynka.
Oznaczmy przez sumaryczną liczbę SKS jedynek w reprezentacjach
binarnych liczb od 1 do .
Na przykład,
, , , .
Chcemy przetwarzać bardzo duże liczby.
Będziemy je więc reprezentować w postaci zwartej.
Jeśli jest dodatnią liczbą całkowitą, jest jej zapisem binarnym
(zaczynającym się od 1), to zwartą reprezentacją jest ciąg
złożony z dodatnich liczb całkowitych, które odpowiadają długościom
kolejnych bloków takich samych cyfr.
Na przykład:
Twoim zadaniem jest napisanie programu, który oblicza ciąg na podstawie .
Wejście
Pierwszy wiersz standardowego wejścia zawiera jedną liczbę całkowitą
(), oznaczającą długość zwartej reprezentacji dodatniej liczby całkowitej .
Drugi wiersz standardowego wejścia zawiera liczb całkowitych ,
() pooddzielanych pojedynczymi odstępami.
Ciąg liczb jest zwartą reprezentacją dodatniej liczby całkowitej .
Dodatkowo możesz założyć, że , czyli .
Wyjście
Twój program powinien wypisać na standardowe wyjście dwa wiersze.
W pierwszym z nich powinna znajdować się jedna dodatnia liczba całkowita .
W drugim wierszu powinno znaleźć się dodatnich liczb całkowitych ,
pooddzielanych pojedynczymi odstępami.
Ciąg powinien być zwartą reprezentacją liczby .
Przykład
Dla danych wejściowych:
6
1 1 1 1 1 1
poprawną odpowiedzią jest:
5
1 1 2 1 1
Wyjaśnienie do przykładu:
Ciąg jest zwartą reprezentacją , ,
natomiast ma zwartą reprezentację .
Autor zadania: Wojciech Rytter.