Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

MWPZ06Y - Binarny ciąg leksykograficzny

Rozważmy wszystkie ciągi binarne o pewnej długości, które składają się tylko z zer i jedynek, a w których żadne dwie jedynki nie stoją obok siebie. To znaczy, że na przykład ciąg 110 nie jest takim ciągiem długości 3 i nie będziemy go uwzględniać, natomiast ciąg 0101 jest takim ciągiem długości 4.

Napisz program, który znajduje ciąg, który jest K-tym spośród wyżej opisanych ciągów uporządkowanych rosnąco w porządku leksykograficznym.

Wejście

Pierwsza linia wejścia zawiera liczbę całkowitą D (1 ≤ D ≤ 500), która określa liczbę zestawów danych. Druga linia składa się z dwóch dodatnich liczb całkowitych N oraz K (0 < N < 44, 0 < K < 1000000000) oznacających odpowiednio długość rozpatrywanych ciągów binarnych oraz miejsce w porządku leksykograficznym poszukiwanego ciągu.

Wyjście

Dla każdego zestawu danych program powinien wypisywać w osobnej linii odnaleziony ciąg albo liczbę −1, jeśli liczba K jest większa niż liczba opisanych ciągów.

Przykład

Wejście:

3
31
32
3599

Wyjście:

000
001
-1


Dodane przez:Rafal Nowak
Data dodania:2006-12-07
Limit czasu wykonania programu:1s
Limit długości kodu źródłowego50000B
Limit pamięci:1536MB
Cluster: Cube (Intel G860)
Języki programowania:All except: GOSU
Pochodzenie:Mistrzostwa Wielkopolski w Programowaniu Zespołowym, 2006

© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.