Atenţie! Aceasta este o versiune veche a paginii, scrisă la 2013-06-14 12:13:09.
Revizia anterioară Revizia următoare

Fişierul intrare/ieşire:	lru.in, lru.out	Sursă	Lot Baia Mare 2013 - Baraj 2 Seniori
Autor	Adrian Panaete, Alexandru Cazacu	Adăugată de	Daniel Constantin Anghel •Magnvs
Timp execuţie pe test	0.2 sec	Limită de memorie	65536 kbytes
Scorul tău	N/A	Dificultate	N/A

Lru

Adrian Wonder Boy tocmai a primit un joc nou. Acesta constă din n triunghiuri echilaterale situate în plan vertical având o latură orizontală şi vârful opus acesteia îndreptat în sus. Triunghiurile au laturile de lungime 1,2,3,…,n şi sunt incluse unul în altul astfel încât oricare două triunghiuri consecutive au un unghi comun. Mai precis, un triunghi mic (de latură i; în desen i=3) poate fi în exact urmatoarele 3 poziţii faţă de triunghiul mai mare (de latură i+1) :


L. triunghiul mic este “în stânga”.	R. triunghiul mic este “în dreapta”.	U. triunghiul mic este “sus”.

Starea jocului la un moment dat poate fi codificată printr-un şir de n-1 caractere ‘L’ , ‘R’ sau ‘U’ care descriu poziţia fiecărui triunghi de latura i (1<=i<n) faţă de triunghiul de latură i+1. De exemplu pentru n=4 în figurile de mai jos avem trei stări ale jocului împreună cu codificările acestora.


Starea 1: RLL	Starea 2: RLU	Starea 3: LRU

Starea jocului poate fi modificată prin glisarea unuia dintre triunghiurile interioare pe direcţia uneia dintre laturi într-un sens sau altul, cu exact o unitate. De exemplu glisând orizontal spre dreapta triunghiul de latură 2 se poate trece din starea 2 în starea 3. Faţă de triunghiul de latură 3, triunghiul de latură 2 a trecut din stânga în dreapta. (Reţineţi faptul că prin glisarea unui triunghi cele interioare lui rămân pe poziţia veche, deci unele mutări nu sunt posibile. De exemplu, în starea 1 triunghiul de latură 2 nu poate glisa în sus deoarece triunghiul de latură 1 ar rămâne în afara triunghiului de latură 2)

Pentru mai multe teste, cunoscând n şi două stări ale jocului, să se determine numărul minim de glisări în urma cărora jocul trece din prima stare în a doua stare.

Date de intrare

Pe prima linie a fişierului lru.in avem un număr natural t- numărul de teste. Următoarele 3*t linii descriu cele t teste, un test pe câte 3 linii. Prima linie dintre cele 3 conţine un număr natural n – lungimea comună a codificării celor două stări. A doua linie dintre cele 3 conţine un şir de n caractere – codificarea stării iniţiale. A treia linie dintre cele 3 conţine un sir de n caractere – codificarea stării finale.