| Fişierul intrare/ieşire: | salsa.in, salsa.out | Sursă | Grigore Moisil 2018, 11-12 |
| Autor | Alex Cociorva | Adăugată de |  Grigore Moisil •grigore.moisil |
| Timp execuţie pe test | 0.15 sec | Limită de memorie | 65536 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
Salsa
Recent, Bulănel a început să ia cursuri de salsa. Fiind un dansator desăvârşit, a învăţat rapid N figuri numerotate de la 1 la N pe care le poate folosi la petreceri. Pentru fiecare figură i, el ştie exact o figură, nextMove[i], cu care poate continua. Fiecare figură durează o secundă pentru a fi executată.
Melodiile de la petreceri au lungimi variate. Curios din fire, Bulănel se întreabă câteodată în câte moduri poate să danseze pe o melodie de X secunde. Pentru că nu vrea să plictisească fetele, pe parcursul melodiei Bulănel va trebui sa folosească doar figuri diferite. Acesta poate începe cu orice figură doreşte.
Ajutaţi-l pe Bulănel să afle în câte moduri poate să danseze pe o melodie de i secunde pentru fiecare i între 1 şi N. Două moduri se consideră diferite dacă există un indice i, astfel încât figurile efectuate la secunda i în cele două moduri sunt diferite.
Date de intrare
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.
Date de ieşire
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.
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".
Exemplu
| salsa.in | salsa.out |
|---|---|
| 4 4 1 2 2 | 4 4 4 1 |
| 3 2 3 1 | 3 3 3 |
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.
