Fişierul intrare/ieşire:maxpal.in, maxpal.outSursăONI 2009 - baraj
AutorZoltan SzaboAdăugată deandrei-alphaAndrei-Bogdan Antonescu andrei-alpha
Timp execuţie pe test0.05 secLimită de memorie20480 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Maxpal

Şirul cu n elemente x1, x2,..., xn se numeşte palindrom dacă este identic cu şirul xn, xn-1,..., x1. Se defineşte subşir al şirului x o submulţime a elementelor şirului x aflate nu neapărat pe poziţii succesive, în care poziţiile relative dintre două elemente se păstrează: xi1, xi2,..., xik, cu 1 ≤ i1 < i2 <...< ikn. Vom numi i1,i2,...,ik şirul indicilor. Două subşiruri se consideră distincte dacă cele două şiruri de indici corespunzătoare celor două subşiruri diferă prin cel puţin un element. De exemplu pentru şirul x=( 1, 3, 5, 6, 3, 5, 1) subşirul ( 1, 3, 5) poate fi corespondentul a trei subşiruri distincte (x1, x2, x3), (x1, x2, x6), (x1, x5, x6), dar nu poate fi corespondentul subşirului (x1, x5, x3), pentru că în acest caz s-a inversat poziţia relativă a elementelor x3 şi x5. Subşirul (x1, x2, x3,x5,x7) = ( 1, 3, 5, 3, 1) este un subşir palindrom.

Cerinta

Cunoscând elementele unui şir, să se calculeze lungimea maximă a unui subşir palindrom şi numărul de subşiruri distincte de lungime maximă.

Date de intrare

Fişierul de intrare maxpal.in conţine două linii. Pe prima linie se află un număr natural reprezentând valoarea lui N iar pe linia următoare cele N elemente ale şirului x, separate prin câte un spaţiu.

Date de ieşire

Fişierul de ieşire maxpal.out va conţine pe o singură linie două numere naturale separate printr-un spaţiu; prima va reprezenta lungimea maximă a unui subşir palindrom iar a doua restul împărţirii numărului de subşiruri palindrom distincte de lungime maximă la numărul 666013.

Restricţii

  • 3N2000
  • 0xi255
  • Pentru răspuns corect la prima cerinţă se acordă 30% din punctaj, iar pentru a doua 70%

Exemplu

maxpal.inmaxpal.out
5
2 1 4 2 2
3 5

Explicaţie

Cel mai lung subşir palindrom are lungimea 3. Avem 5 soluţii distincte:
(x1, x2, x4)=( 2, 1, 2)
(x1, x2, x5)=( 2, 1, 2)
(x1, x3, x4)=( 2, 4, 2)
(x1, x3, x5)=( 2, 4, 2)
(x1, x4, x5)=( 2, 2, 2)

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content