Fişierul intrare/ieşire:	spion.in, spion.out	Sursă	ONI 2014, clasa a 10-a
Autor	Vlad Nicu	Adăugată de	Tudor Varan •tudorv96
Timp execuţie pe test	0.15 sec	Limită de memorie	20480 kbytes
Scorul tău	N/A	Dificultate	1/5

Vezi solutiile trimise | Statistici

Spion

Spionul 008 vrea să găsească o locaţie secretă în junglă, având asupra lui un dispozitiv de localizare. Iniţial spionul se află la intrarea în junglă pe nivelul 1 şi cu fiecare pas, el avansează de la nivelul i la nivelul i+1, ajungând la locaţia secretă, aflată pe ultimul nivel, în poziţia u faţă de marginea stângă a nivelului curent. Pentru a ajunge în locaţia secretă, el poate să se deplaseze cu o poziţie spre Sud-Est (codificat cu caracterul E) sau spre Sud-Vest (codificat cu caracterul V), trecând de pe nivelul i pe nivelul i+1 cu viteză constantă. Numărul de poziţii de pe un nivel creşte cu unu faţă de nivelul anterior, conform imaginii alăturate. Numim traseu o succesiune formată din caractereleE sau V, corespunzătoare deplasării spionului de pe nivelul 1 la locaţia secretă. Pentru exemplul din figura alăturată succesiunea de caractere VEEVE reprezintă un traseu ce corespunde locaţiei secrete din poziţia 4 a nivelului 6.

Cerinţă

Cunoscând succesiunea de caractere corespunzătoare unui traseu, determinaţi:
a) poziţia locaţiei secrete de pe ultimul nivel;
b) numărul de trasee distincte pe care le poate urma spionul plecând din poziţia iniţială pentru a ajunge în locaţia secretă corespunzătoare traseului dat. Două trasee se consideră distincte dacă diferă prin cel puţin o poziţie.

Date de intrare

Fişierul de intrare spion.in conţine pe prima linie un număr natural p egal cu 1 sau 2, iar pe a doua linie o succesiune de caractere corespunzătoare unui traseu.

Date de ieşire

Dacă valoarea lui p este 1, atunci se va rezolva numai punctul a) din cerinţă. În acest caz, fişierul de ieşire spion.out va conţine pe prima linie un număr natural ce reprezintă poziţia de pe nivelul final a locaţiei secrete.
Dacă valoarea lui p este 2, atunci se va rezolva numai punctul b) din cerinţă. În acest caz, fişierul de ieşire spion.out va conţine pe prima linie un număr natural ce reprezintă numărul de trasee distincte
modulo 100.003.

Restricţii

• 2 ≤ lungimea şirului paşilor ≤ 100 000;
• pentru 20% din teste valorea lui p=1;
• pentru alte 10% din teste valoarea lui p=2 şi lungimea secvenţei de caractere ≤ 255;
• pentru alte 10% din teste valoarea lui p=2 şi 300 ≤ lungimea secvenţei de caractere ≤ 1900;
• pentru alte 10% din teste valoarea lui p=2 şi 3000 ≤ lungimea secvenţei de caractere ≤ 5000.

Exemplu

Explicaţie

Pentru primul exemplu locaţia secretă este în poziţia 4 de pe nivelul 6.

Pentru al doilea exemplu există trei trasee: VVE, VEV, EVV.

Cum se trimit solutii?