.campion
conectare | înregistrare | căutare
Pagina principală » Probleme » spion1

ultima problemă
grupă: mică
sursă: OMI 2016
ultimul articol
autor: Prof. Radu Vişinescu
ultimul software
autor: Prof. Emanuela Cerchez
spion1


Timp maxim de execuţie / test:
0.1s
Memorie totala disponibilă / stivă:
16MB / 8MB

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 spion1.in conţine pe prima linie un număr natural p din {1,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 spion1.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 spion1.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.

Exemple

spion1.inspion1.outExplicaţii
1 VEEVE 4 Locaţia secretă este în poziţia 4 de pe nivelul 6.
2 VEV 3 Există trei trasee: VVE, VEV, EVV.
2 EVEVVEVEEE 210

autor: Prof. Vlad Laurentiu Nicu
propunător: Prof. Emanuela Cerchez
Colegiul Naţional ″Emil Racoviţă″
emanuela.cerchez@gmail.com
Articole recomandate
Probleme recomandate
surse trimise | ajutor