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.
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 .
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 .
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 .
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.