Fişierul intrare/ieşire:salsa.in, salsa.outSursăGrigore Moisil 2018, 11-12
AutorAlex CociorvaAdăugată degrigore.moisilGrigore Moisil grigore.moisil
Timp execuţie pe test0.3 secLimită de memorie65536 kbytes
Scorul tăuN/ADificultateN/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.insalsa.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.

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?