Fişierul intrare/ieşire:ccount.in, ccount.outSursăad-hoc
AutorMihai CalanceaAdăugată deklamathixMihai Calancea klamathix
Timp execuţie pe test0.3 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(intreg n) {
  daca A(n) este cunoscut atunci intoarce valoarea A(n); 
  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.
  • Dupa apelarea functiei F(n), valoarea A(n) nu devine cunoscuta in continuare. Astfel, F(n) va fi apelata de oricate ori este nevoie pentru o anumita valoare a lui n.
  • 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
3

Explicaţie

Variabila calcule_totale este incrementata in apelurile F(6), F(4), F(3).
Observati ca daca A(5) nu ar fi fost cunoscut, raspunsul ar fi fost 7.

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?