Fişierul intrare/ieşire:consir.in, consir.outSursăAutumn Warmup 2007, Runda 3
AutorAdrian AirineiAdăugată deastronomyAirinei Adrian astronomy
Timp execuţie pe test0.45 secLimită de memorie20480 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Consir

Vultur a gasit in cartea de chimie o problema pe care nu stie sa o rezolve si are nevoie de ajutorul vostru. Se da o secventa A, formata din N numere naturale. Un consir este un sir de numere naturale i1, i2 ... ip (cu valori cuprinse intre 1 si N) cu proprietatea ca A[i1], A[i2] ... A[ip] sunt numere consecutive. Mai exact A[i2]=A[i1]+1, A[i3]=A[i2]+1 ... A[ip]=A[ip-1]+1. Determinati K, lungimea maxima a unui consir ce se poate forma, precum si numarul de consiruri distincte de lungime 1, 2 ... K.

Date de intrare

Pe prima linie a fisierului consir.in se va afla numarul N avand semnificatia din enunt. Pe urmatoarele N linii se afla valorile secventei A, mai exact pe linia i+1 se afla valoarea lui A[i].

Date de iesire

Pe prima linie a fisierului consir.out se va afla valoarea K, avand semnificatia din enunt. In continuare vor urma K linii, pe linia i+1 aflandu-se numarul de consiruri distincte de lungime i.

Restrictii

  • 1 ≤ N ≤ 310 000
  • Termenii sirului au valori cuprinse intre 1 si 1 000 000
  • Se garanteaza ca fiecare raspuns are o valoare mai mica decat 263 (se incadreaza pe tipuri de date intregi pe 64 biti fara semn)
  • Lungimea unui consir este data de numarul de elemente
  • Doua consiruri X si Y sunt distincte daca exista o pozitie i astfel incat Xi diferit de Yi
  • In cel putin 30% din teste N ≤ 1000

Exemplu

consir.inconsir.out
6
1
2
1
3
4
5
5
6
5
4
3
2

Explicatie

Cele 2 consiruri de lungime 5 sunt 1 2 4 5 6 si 3 2 4 5 6
Cele 3 consiruri de lungime 4: 1 2 4 5, 3 2 4 5 si 2 4 5 6
Cele 4 consiruri de lungime 3: 1 2 4, 2 4 5, 3 2 4 si 4 5 6
Cele 5 consiruri de lungime 2: 1 2, 2 4, 4 5, 3 2 si 5 6
Cele 6 consiruri de lungime 1: 1, 2, 3, 4, 5 si 6

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content