Polish version    English version  
  Obozy Olimpiady


 Aktualności
 O olimpiadzie
 Komitety
 XVIII OI 2010/2011
 Historia OI
 Książeczki OI
 Reprezentacja
 Obozy Olimpiady
III obóz 2002
IV obóz 2003
V obóz 2004
VI obóz 2005
 Galeria zdjęć
 Ciekawe odsyłacze
 OIG LiveCD
 IV OIG 2009/2010
 Historia OIG
 SIO
 MAIN
III Obóz im. A. Kreczmara 2002

Zadanie: lin
Autor: Krzysztof Onak
Linochodziarz

dzień drugi 6 sierpnia 2002
Plik źródłowy: lin.??? (np. pas, c, cpp)
Plik wejściowy: lin.in
Plik wyjściowy: lin.out

Linochodziarz chodzi po osi liczbowej i dysponuje dwoma zestawami kroków - do przodu i do tyłu - które wykonuje na przemian. Przyjmijmy, że mamy dwa niepuste zbiory dodatnich liczb całkowitych A i B. Linochodziarz startuje z punktu 0 i w nieskończonej pętli wykonuje następujące czynności: idzie a (liczba a należy do zbioru A) kroków do przodu (w kierunku plus nieskończoności), zatrzymuje się, cofa się o b (b należy do B) kroków i znów się zatrzymuje. W kolejnych iteracjach pętli mogą występować różne wartości a i b. Interesuje nas odpowiedź na pytanie, czy dla danych zbiorów A i B linochodziarz może zatrzymać się w każdym punkcie całkowitym.

Zadanie

Napisz program, który:

  • wczyta z pliku tekstowego lin.in zestawy danych opisujące różne pary zbiorów A i B,
  • dla każdego zestawu danych rozstrzygnie, czy dana para zbiorów A i B pozwala na to, aby linochodziarz zatrzymał się w każdym punkcie całkowitym,
  • zapisze wynik w pliku tekstowym lin.out.

Wejście

W pierwszym wierszu pliku tekstowego lin.in znajduje się jedna liczba całkowita k określająca liczbę zestawów danych, 1 <= k <= 100. Po niej następuje k zestawów danych. W pierwszym wierszu każdego z nich znajdują się liczby całkowite p i q (1 <= p,q <= 1000) oddzielone pojedynczym odstępem. Są to odpowiednio liczba elementów w zbiorze A i w zbiorze B. Następne p+q wierszy zawiera po jednej dodatniej liczbie całkowitej nie większej niż 109. Pierwsze p z tych liczb jest elementami zbioru A, a następne q należy do B.

Wyjście

Plik tekstowy lin.out powinien zawierać k wierszy. Wiersz i-ty powinien zawierać jedno słowo TAK, jeśli linochodziarz opisany w i-tym zestawie danych może zatrzymać się w każdym punkcie całkowitym, lub słowo NIE w przeciwnym przypadku.

Przykład

Dla pliku wejściowego lin.in:

2
1 1
2
2
2 2
1
2
1
2

poprawną odpowiedzią jest plik wyjściowy lin.out:

NIE
TAK



Wersja do druku