h2. Date de intrare
Fişierul de intrare $salsa.in$ ...
Fişierul de intrare salsa.in conţine pe prima linie un număr întreg $N$, reprezentând numărul total de figuri. Următoarea linie conţine $N$ numere întregi, al $i$-lea dintre acestea reprezentând $nextMove[i]$, figura care se poate executa după figura $i$.
h2. Date de ieşire
În fişierul de ieşire $salsa.out$ ...
Fişierul de ieşire $salsa.out$ trebuie să conţină $N$ numere întregi, al $i$-lea dintre acestea reprezentând răspunsul pentru întrebarea $i$ - mai exact, în câte moduri poate Bulănel să danseze pe o melodie de $i$ secunde.
h2. Restricţii
* $... ≤ ... ≤ ...$
* $2 ≤ N ≤ 100 000$
* Se garantează că $nextMove[i] ≠ i$ şi $1 ≤ nextMove[i] ≤ N$, pentru orice $i$ intre $1$ şi $N$.
* Pentru unele teste în valoare de $10$ puncte, se garantează că şirul $nextMove[]$ va avea toate elementele distincte.
* Pentru alte teste în valoare de $10$ puncte, se garantează că $2 ≤ N ≤ 1 000$.
* Problema va fi evaluată pe teste în valoare de $90$ de puncte.
* Exemplele vor reprezenta teste în valoare de $10$ puncte "din oficiu".
h2. Exemplu
table(example). |_. salsa.in |_. salsa.out |
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
| 4
4 1 2 2
| 4
4
4
1
|
| 3
2 3 1
| 3
3
3
|
h3. Explicaţie
...
La primul exemplu:
Pentru o melodie de $1$ secundă, Bulănel poate executa $4$ secvenţe valide de figuri: $1, 2, 3, 4$.
Pentru o melodie de $2$ secunde, Bulănel poate executa $4$ secvenţe valide de figuri: $1-4, 2-1, 3-2, 4-2$.
Pentru o melodie de $3$ secunde, Bulănel poate executa $4$ secvenţe valide de figuri: $1-4-2, 2-1-4, 3-2-1, 4-2-1$.
Pentru o melodie de $4$ secunde, Bulănel poate executa doar o secvenţă validă de figuri: $3-2-1-4$.
== include(page="template/taskfooter" task_id="salsa") ==
