 |
| Aktualności |
| O olimpiadzie |
| Komitety |
| XVIII OI 2010/2011 |
| Historia OI |
| Książeczki OI |
| Reprezentacja |
| Obozy Olimpiady |
| Galeria zdjęć |
| Ciekawe odsyłacze |
| OIG LiveCD |
| IV OIG 2009/2010 |
| Historia OIG |
| SIO |
| MAIN |
|
X Olimpiada Informatyczna 2002/2003
|
|
Zadanie: tro
|
Autor: Krzysztof Sikora
|
Trójmian
| 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.
Zadanie
Napisz program, który:
- wczyta ze standardowego wejścia zestawy danych w których są liczby n oraz i,
- dla każdego zestawu obliczy resztę z dzielenia przez 3 współczynnika ci stojącego przy xi w rozwinięciu wielomianu (x2 + x + 1)n,
- dla każdego zestawu wypisze na standardowe wyjście obliczoną resztę.
Wejście
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.
Wyjście
Na standardowe wyjście należy wypisać k wierszy. Wiersz j-ty powinien zawierać jedną dodatnią liczbę całkowitą będąca resztą z dzielenia ci przez 3 dla liczb z j-tego zestawu.Przykład
Dla danych wejściowych:
5 2 0 7 4 4 5 5 3 8 15
poprawnym wynikiem jest:
1 2 1 0 2