Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

MWP3_3E - Emocjonująca rozgrywka w węża

Zapewne wszyscy z Was znają grę w węża, która to była jedną z najpopularniejszych gier dla telefonów komórkowych. Gra w ostatnich czasach mocno się rozwinęła uzyskując nową funkcjonalność: 3D, multiplayer itp. My jednak zajmiemy się starym dobrym dwuwymiarowym wężem znanym chociażby z Nokii 3210. Otóż nasz wąż porusza się po nieskończenie dużej planszy. Z każdej z jej komórek możemy skręcić w prawo, w lewo albo pójść prosto. Oczywiście nasz wąż może też zjadać znajdujące się na planszy elementy, w końcu na tym polega ta gra aby spożyć ich jak najwięcej. Zjedzenie jednego elementu powoduje wydłużenie się węża o ten właśnie element np. wąż znajdujący się na polach 0 0 (głowa), 1 0, 2 0 zjada element znajdujący się na polu -1 0, po zjedzeniu wąż składa się z pól -1 0 (głowa), 0 0, 1 0, 2 0. Twoim zadaniem będzie sprawdzenie na podstawie wczytanych na wejściu ruchów węża czy gra zakończy się wraz z ostatnim ruchem czy też wąż zginie gryząc sam siebie. Początkowa długość węża wynosi 1.

Wejście

W pierwszej linii wejścia znajduje się jedna liczba naturalna Z (1 ≤ Z ≤ 1000) określająca ilość zestawów danych. W kolejnych liniach znajdują się zestawy danych.

W pierwszej i jedynej linii każdego zestawu danych znajduje się jedna liczba naturalna n (1 ≤ n ≤ 2400), określająca ilość ruchów jakie wykona wąż oraz n znaków określających te ruchy. Każdy znak to jedna z czterech liter: L, R, F, albo E. L - wąż przechodzi na pole po swojej lewej stronie, R - wąż przechodzi na pole po swojej prawej stronie, F - wąż przechodzi na pole przed sobą, E - wąż przechodzi na pole przed sobą i zjada znajdujący się na nim element.

Wyjście

Dla każdego zestawu danych należy w osobnej linii wypisać słowo "TAK" jeżeli wąż przejdzie zwycięsko grę albo numer porządkowy ruchu w którym ugryzł samego siebie. Numerację ruchów zaczynamy od 1.

Przykład

Wejście:

2
6 FLERFF
8 EEEELLLL

Wyjście:

TAK
7

Dodane przez:Maciej Boniecki
Data dodania:2010-12-17
Limit czasu wykonania programu:0.100s
Limit długości kodu źródłowego50000B
Limit pamięci:1536MB
Cluster: Cube (Intel G860)
Języki programowania:All except: ASM64 GOSU
Pochodzenie:III Mistrzostwa WWSI w Programowaniu
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.