Atenţie! Aceasta este o versiune veche a paginii, scrisă la 2012-12-15 09:43:35.
Revizia anterioară   Revizia următoare  

 

Fişierul intrare/ieşire:ccount.in, ccount.outSursăad-hoc
AutorMihai CalanceaAdăugată deklamathixMihai Calancea klamathix
Timp execuţie pe test0.15 secLimită de memorie20480 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Ccount

Fie urmatorul sir:

A(1) = 1.
A(2) = 1.
A(i) = x * A(i - 1) + y * A(i - 2), pentru orice i mai mare sau egal cu 3.

Se da o lista de pozitii P1, P2.. Pk, cu semnificatia ca valorile A(P1), A(P2), ... A(Pk) sunt cunoscute. Se considera ca valorile A(1) si A(2) sunt de-asemenea cunoscute, chiar daca numerele 1 si 2 s-ar putea sa nu fie incluse in lista P.

Procedura de calcul pentru un anumit termen al sirului, fie el A(n) este urmatoarea:

intreg F(n) {

  daca A(n) este cunoscut atunci intoarce valoarea A(n); // retineti ca in momentul in care functia intoarce o valoare apelul functiei este finalizat.
  calcule_totale++;  
  intoarce valoarea F(n - 1) + F(n - 2);
}

Care va fi valoarea variabilei globale calcule_totale dupa ce apelam F(n)?
Deoarece acest numar poate fi foarte mare, rezultatul se va afisa mod 9007.

Date de intrare

Fişierul de intrare ccount.in va contine pe prima sa linie numarul N si numarul K, reprezentand indicele termenului pentru care oferim raspunsul, respectiv numarul de elemente al listei P.
Cea de a doua linie va contine K numere, reprezentand lista P.

Date de ieşire

În fişierul de ieşire ccount.out se va afla raspunsul problemei mod 9007.

Restricţii

  • 1 ≤ N ≤ 105
  • A mod B se refera la restul impartirii numarului A la numarul B.
  • Urmatoarele relatii sunt valabile si pot fi necesare pentru a calcula rezultatul fara a depasi tipurile de date C++:
  • (A + B) mod C = (A mod C + B mod C) mod C
  • (A * B) mod C = ((A mod C) * (B mod C)) mod C

Exemplu

ccount.inccount.out
6 1
5
This is another
text written on
multiple lines.

Explicaţie

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?