Rezolvare completă PbInfo #1110 Spion1

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 și precizări

  • 2 ≤ lungimea şirului paşilor ≤ 100 000;
  • pentru 20% din teste valoarea 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.
h1. Exemplul 1

spion1.in

1
VEEVE

spion1.out

4

Explicație

Locația secretă este în poziţia 4 de pe nivelul 6.

Exemplul 2

spion1.in

2
VEV

spion1.out

3

Explicație

Există trei trasee: VVE, VEV, EVV.

Exemplul 3

spion1.in

2
EVEVVEVEEE

spion1.out

210

Cum e corect?

cout < "As la info"; cout << "As la info"; cout >> "As la info";

Felicitări! Poți mai mult?

Avem sute de probleme pentru tine, fiecare cu explicații ușor de înțeles.

Greșit, dar nu-i bai!

Antrenează-te cu sutele de probleme pe care ți le-am pregătit. Îți explicăm fiecare problemă în parte.

Rezolvare

Iată rezolvarea de 100 de puncte pentru problema Spion1:

//Nicu Vlad-Laurentiu Liceul Mihail Kogalniceanu Vaslui
#include <fstream>
#include <cstring>
using namespace std;
const int N=100005, MOD=100003;
ifstream fin("spion1.in");
ofstream fout("spion1.out");
int fact[N],p;
char a[N];
int pw(int x, int y)
{
    int ret=1;
    for(;y;y>>=1)
    {
        if(y&1)
        {
            ret=(1LL*ret*x)%MOD;
        }
        x=(1LL*x*x)%MOD;
    }
    return ret;
}
void init(int n)
{
    int i;
    fact[1]=1;
    for(i=2;i<=n;i++) fact[i]=(1LL*fact[i-1]*i)%MOD;
}
int comb(int n, int k)
{
    if(!n||!k) return 1;
    return 1LL*fact[n]*pw(1LL*fact[k]*fact[n-k]%MOD, MOD-2)%MOD;
}
int main()
{
    int i, n, x=0, y=0;
    fin>>p;fin.get();
    fin.getline(a,N);
    n=strlen(a);
    init(n);
    for(i=0;i<n;i++)
    {
        if(a[i]=='E') y++;
        x++;
    }
    if(p==1)
    fout<<y+1<<"\n";
    else fout<<comb(x, y)<<"\n";
}

Atenție

Enunțurile afișate pe această pagină aparțin exclusiv site-ului PbInfo. Astfel, pentru ștergerea conținutului, puteți să ne contactați la adresa Adresa de email.

Rezolvarea problemei #1110 Spion1

Pe această pagină găsești rezolvarea de 100 de puncte pentru problema #1110 Spion1 de pe PbInfo.ro. Atenție: nu încurajăm copiatul codului! Totuși, credem cu tărie că analizarea unei soluții corecte este o metodă foarte ușoară de a învăța informatică, astfel că oferim sursele pentru peste 1500 de probleme de pe platforma PbInfo.ro.

Pentru rezolvări PbInfo de la peste 1500 de probleme, vă invităm să intrați pe site-ul nostru!