X Olimpiada Informatyczna 2002/2003
|
Zadanie: tro
|
Autor: Krzysztof Sikora
|
Zawody II stopnia, dzień pierwszy |
Plik źródłowy: | tro.xxx (xxx=pas,c,cpp) |
Alternatywne formaty: PostScript | PDF
Rozważmy wielomian (x2 + x + 1)n. Interesują nas współczynniki ci rozwinięcia tego wielomianu:
c0 + c1x + c2x2 + ... + c2n x2n
Na przykład, (x2 + x + 1)3 = 1 + 3x + 6x2 + 7x3 + 6x4 + 3x5 + x6.
Napisz program, który:
W pierwszym wierszu standardowego wejścia znajduje się jedna liczba całkowita k określająca liczę zestawów danych, 1 <= k <= 10000. Po niej następuje k zestawów danych, po jednym w wierszu. W każdym zestawie danych zapisane są dwie nieujemne liczby całkowite n oraz i oddzielone pojedynczym odstępem, 0 <= n <= 1000000000000000, 0 <= i <= 2n.
Dla danych wejściowych:
5 2 0 7 4 4 5 5 3 8 15
poprawnym wynikiem jest:
1 2 1 0 2