XI Wiosenny Turniej w Programowaniu Zespołowym Politechnika Poznańska, 26 V 2007

Opis

W tym zadaniu słowo stringi odnosi się do łańcuchów DNA, a nie do części garderoby. Sorry. Zadanie jest następujące:

Mamy dane N łańcuchów DNA. Wiemy że wszystkie łańcuchy oprócz maksymalnie jednego są poprawne. Natomiast możliwe jest, iż wśród nich znajduje się jeden łańcuch zmutowany. Mutant różni się tym od łańcucha poprawnego, iż ma inną zasadowość. Aby znaleźć mutanta przeprowadzamy szereg doświadczeń. Doświadczenie polega na wrzuceniu pewnej liczby łańcuchów, którymi dysponujemy do dwóch naczyń z roztworem. Kolor naczynia będzie odzwierciedlał sumaryczną zasadowość łańcuchów DNA tam się znajdujących. Dysponując bardzo dokładnymi przyrządami pomiarowymi jesteśmy w stanie powiedzieć, który roztwór ma większą zasadowość lub stwierdzić, że oba mają identyczną zasadowość. Niestety mamy ograniczony budżet i wolno nam wykonać tylko K doświadczeń. Czy to wystarczy, aby w każdym przypadku znaleźć mutanta?

Uwaga: Każdy, kto troche zna się na biologii wie, że nie ma problemu, żeby po doświadczeniu wyjąć nasze łańcuchy DNA z roztworów. Jak ktoś nie wierzy, to niech sobie w domu sprawdzi.

Specyfikacja wejścia

W pierwszym wierszu znajduje się liczba oznaczająca liczbę następujących testów. W każdym kolejnym wierszu znajduje się opis jednego testu w postaci dwóch liczb: N, K (0 ≤ N,K ≤ 2000000000).

Specyfikacja wyjścia

Dla każdego testu wypisz TAK, jeśli da się jednoznacznie stwierdzić, czy wśród naszych łańcuchów jest mutant (i jeśli tak, to czy da się go wskazać), bądź też NIE w przeciwnym wypadku.

Przykład

2
4 2
3 2

NIE
TAK