Kodowanie

27.10.2010
Trudność

Kodowanie

Limit czasowy: 1000 milisekund
Limit pamięciowy: 32000 kilobajtów


Pawła, studenta informatyki na Uniwersytecie Wrocławskim, w ostatnim semestrze bardzo zaciekawiły problemy poruszane na przedmiocie Kompresja danych. Jako zdolny uczeń, Paweł postanowił wymyślić nowy sposób na kompresję sekwencji liczb naturalnych.

Pierwszym krokiem algorytmu Pawła jest zamiana ciągów liczb naturalnych na ciągi liczb zapisanych binarnie. Nie można zrobić tego tak po prostu - trzeba umieć oddzielać kolejne kodowane liczby używając tylko zer i jedynek. W tym celu, Paweł postanowił wykorzystać dwie sąsiednie jedynki jako znacznik końca pojedynczej liczby. Ta metoda pociąga za sobą jednak pewne konsekwencje. Aby móc rozdzielać kolejne elementy ciągu, binarny kod żadnej z liczb nie może zawierać dwóch sąsiednich jedynek, a także musi zaczynać się od jedynki.

Chcąc zbadać skuteczność kompresji, Paweł potrzebuje wiedzieć ile różnych liczb jest w stanie zakodować używając n bitów. Niestety, Paweł w obecnym semestrze ma sporo pracy - poprosił więc Ciebie o pomoc. Twoim zadaniem jest napisanie programu, który dla podanej wartości n obliczy ile jest różnych, binarnych kodów długości n, które zaczynają się od jedynki i nie zawierają dwóch jedynek koło siebie.

 

Wejście:

W pierwszej linii wejścia znajduje się jedna liczba całkowita T (1<=T<=100), oznaczająca ilość zestawów danych. Następnie na wejściu podane są opisy kolejnych zestawów danych. Pojedynczy zestaw danych składa się z jednej linii. Znajduje się w niej jedna liczba całkowita n (1<=n<=45). 


Wyjście:

Dla każdego zestawu danych Twój program powinien wypisać pojedynczą linię zawierającą jedną liczbę całkowitą. Jest to liczba różnych ciągów zero-jedynkowych długości n, które zaczynają się od jedynki i nie zawierają dwóch sąsiednich jedynek.

 

Przykład:

Dla danych wejściowych:

2
1
4

 

poprawną odpowiedzią jest:

1
3

 

Objaśnienie przykładu:

Wszystkie ciągi długości 4, które spełniają podane kryteria to 1000, 1001, 1010.

 

Nie możesz wysyłać i oglądać rozwiązań tego zadania ponieważ nie jesteś zalogowany. Zaloguj się lub załóż konto.
3.5
Twoja ocena: Brak Ocena: 3.5 (8 ocen)

Copyright © 2008-2010 Wrocławski Portal Informatyczny

design: rafalpolito.com