== include(page="template/taskheader" task_id="ccount") ==
Poveste şi cerinţă...
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:
==code(c)| 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*.
h2. Date de intrare
Fişierul de intrare $ccount.in$ ...
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$.
h2. Date de ieşire
În fişierul de ieşire $ccount.out$ ...
În fişierul de ieşire $ccount.out$ se va afla raspunsul problemei *mod 9007*.
h2. Restricţii
* $... ≤ ... ≤ ...$
* $1 ≤ N ≤ 10^5^$
* $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
h2. Exemplu
table(example). |_. ccount.in |_. ccount.out |
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
| 6 1
5
|3
|
h3. 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.
== include(page="template/taskfooter" task_id="ccount") ==
