| Fişierul intrare/ieşire: | maxpal.in, maxpal.out | Sursă | ONI 2009 - baraj |
| Autor | Zoltan Szabo | Adăugată de |  Andrei-Bogdan Antonescu •andrei-alpha |
| Timp execuţie pe test | 0.05 sec | Limită de memorie | 20480 kbytes |
| Scorul tău | N/A | Dificultate | N/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 <...< ik ≤ n. 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
- 3 ≤ N ≤ 2000
- 0 ≤ xi ≤ 255
- Pentru răspuns corect la prima cerinţă se acordă 30% din punctaj, iar pentru a doua 70%
Exemplu
| maxpal.in | maxpal.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)
