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

OIG1_LOT - Lotki

W Bajtocji bardzo popularną jest gra zwana BajtoLotkiem. Na karcie do gry znajdują się wszystkie liczby naturalne od 1 do n. Spośród nich należy skreślić co najmniej a i co najwyżej b liczb. W grze zwycięża ten, kto trafnie wytypuje (skreśli) liczby wylosowane przez maszynę losującą.

Młody informatyk Bajtek pragnie pomóc swojemu tacie, który jest zapalonym graczem. Postanowił w tym celu napisać dla taty program, który mając daną liczbę k obliczy, jaki jest k-ty w kolejności leksykograficznej podzbiór zbioru liczb {1, ..., n}, zawierający co najmniej a i co najwyżej b liczb.

Wejście

W pierwszym wierszu znajduje się jedna liczba całkowita d (1 ≤ d ≤ 1000), oznaczająca liczbę przypadków do rozważenia. Każdy z następnych d wierszy zawiera cztery liczby całkowite n, a, b oraz k (1 ≤ a ≤ b ≤ n ≤ 60), pooddzielane pojedynczymi odstępami i oznaczające odpowiednio: liczbę liczb znajdujących się na karcie, minimalną i maksymalną liczbę liczb do wykreślenia oraz leksykograficzną pozycję szukanego zbioru. Pozycje zbiorów numerujemy od 1.

Wyjście

Wyjście powinno składać się z dokładnie d wierszy. Dla każdego przypadku gry z wejścia powinien zostać wypisany jeden wiersz, zawierający k-ty w kolejności leksykograficznej podzbiór zbioru {1, ..., n} o żądanym rozmiarze. Liczby powinno być wypisane w kolejności rosnącej, pooddzielane pojedynczymi odstępami. Dane na wejściu są tak dobrane, że dla każdego przypadku testowego parametr k jest niewiększy od liczby wszystkich podzbiorów zbioru {1, ..., n}, zawierających między a a b elementów.

Przykład

Wejście:

2
5 2 4 10
5 1 2 7

Wyjście:

1 3 4 5
2 3


Dodane przez:Rafal Nowak
Data dodania:2007-05-25
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:I Olimpiada Informatyczna Gimnazjalistów

ukryj komentarze
2015-04-10 10:51:10 Arkadiusz Nowaczyñski
Hmm... faktycznie, jak teraz to oszacowałem, to wyszło mi, że w najgorszym przypadku wcale nie ma konieczności zastosowania arytmetyki dużych liczb.

Ostatnio edytowany: 2015-04-10 11:00:10
2015-04-10 09:54:34 narbej
sorry, to zadanie jest kat. trudne, i czy taka podpowiedź, nie powinna być mniej widoczna, a jeżeli już, to czy raczej nie powinna być na forum np jako dopisek, do istniejącego już, starego wątku? Nawet w wielu zadaniach, niższej kategorii [trudności] często brakuje takiej informacji i jest to jedno z dodatkowych zadań rozwiązującego [wydedukowanie, obliczenie tego zakresu].


Ostatnio edytowany: 2015-04-10 10:07:06
2015-04-09 21:57:56 Arkadiusz Nowaczyñski
Do wczytania liczby k należy użyć całkowitego typu 64-bitowego.
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.