Atenţie! Aceasta este o versiune veche a paginii, scrisă la 2009-04-21 08:51:47.
Revizia anterioară   Revizia următoare  

 

Fişierul intrare/ieşire:unique.in, unique.outSursăONI 2009 - baraj
AutorAndrei Grigorean, Paul-Dan BaltescuAdăugată deandrei-alphaAndrei-Bogdan Antonescu andrei-alpha
Timp execuţie pe test0.2 secLimită de memorie65536 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Unique

Miruna şi Laura se joacă cu prietena lor cea mai bună, Omida. Miruna are un şir de N numere naturale şi vrea să găsească o subsecvenţă S de lungime maximă care să respecte următoarea proprietate:

* Să conţină cel puţin o dată fiecare număr între 1 şi MaxS, unde MaxS reprezintă valoarea maximă din subsecvenţa S.
Ajutaţi-le pe Laura şi Omida să îi răspundă Mirunei.

Cerinta

Cunoscând elementele unui şir, să se calculeze lungimea maximă a unei subsecvenţe care respectă cerinţa impusă.

Date de intrare

Fişierul de intrare unique.in va conţine:

  • pe prima linie un singur număr natural T, reprezentând numărul de teste din fişier.
  • Pe linia 2i, (i=1,2,...,T) un număr natural reprezentând numărul de elemente dintr-un şir
  • Pe linia 2i+1, (i=1,2,...,T) elementele şirului a cărui lungime este dată pe linia anterioară

Date de ieşire

Fişierul de ieşire unique.out va conţine T linii; pe linia i se va scrie lungimea maximă a unei subsecvenţe a şirului care respectă cerinţa impusă, dat prin liniile 2i şi 2i+1 în fişierul de intrare (i=1,2,...,T).

Restricţii

  • 1T10
  • 1N100000
  • Elementele şirurilor vor fi cuprinse între 1 şi N.

Exemplu

unique.inunique.out
1
16
3 1 4 5 2 7 5 2 8 3 1 3 1 2 3 9
6

Explicaţie

Cea mai lungă subsecvenţă care respectă condiţia impusă începe pe poziţia 10 şi se termină pe poziţia 15.

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?