Polish version    English version  
  Historia OI -> X OI 2002/2003 -> Zadania


 Aktualności
 O olimpiadzie
 Komitety
 XVIII OI 2010/2011
 Historia OI
XVII OI 2009/2010
XVI OI 2008/2009
XV OI 2007/2008
XIV OI 2006/2007
XIII OI 2005/2006
XII OI 2004/2005
XI OI 2003/2004
X OI 2002/2003
Terminarz
Zadania
Wyniki III etapu
Wyniki II etapu
Wyniki I etapu
II Etap
Przepisy
Dla zawodnikow
Przydatne zasoby
IX OI 2001/2002
VIII OI 2000/2001
VII OI 1999/2000
VI OI 1998/1999
V OI 1997/1998
IV OI 1996/1997
III OI 1995/1996
II OI 1994/1995
I OI 1993/1994
 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



Wersja do druku