== include(page="template/taskheader" task_id="maxpal") ==
Şirul cu n elemente x{~1~}, x{~2~},..., x{~n~} se numeşte palindrom dacă este identic cu şirul x{~n~}, x{~n-1~},..., x{~1~}. 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ă: x{~i1~}, x{~i2~},..., x{~ik~}, cu 1 ≤ i{~1~} < i{~2~} <...< i{~k~} ≤ $n$. Vom numi i{~1~},i{~2~},...,i{~k~} ş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 (x{~1~}, x{~2~}, x{~3~}), (x{~1~}, x{~2~}, x{~6~}), (x{~1~}, x{~5~}, x{~6~}), dar nu poate fi corespondentul subşirului (x{~1~}, x{~5~}, x{~3~}), pentru că în acest caz s-a inversat poziţia relativă a elementelor x{~3~} şi x{~5~}. Subşirul (x{~1~}, x{~2~}, x{~3~},x{~5~},x{~7~}) = ( $1$, $3$, $5$, $3$, $1$) este un subşir palindrom.
h2. 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ă.
Poveste şi cerinţă...
h2. 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.
Fişierul de intrare $maxpal.in$ ...
h2. 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$**.
În fişierul de ieşire $maxpal.out$ ...
h2. Restricţii
* $3$ ≤ $N$ ≤ $2000$
* $0$ ≤ $x${~i~} ≤ $255$
* Pentru răspuns corect la prima cerinţă se acordă $30$% din punctaj, iar pentru a doua $70$%
* $... ≤ ... ≤ ...$
h2. Exemplu
table(example). |_. maxpal.in |_. maxpal.out |
| 5
2 1 4 2 2
| 3 5
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
|
h3. Explicaţie
Cel mai lung subşir palindrom are lungimea $3$. Avem $5$ soluţii distincte:
(x{~1~}, x{~2~}, x{~4~})=( $2$, $1$, $2$)
(x{~1~}, x{~2~}, x{~5~})=( $2$, $1$, $2$)
(x{~1~}, x{~3~}, x{~4~})=( $2$, $4$, $2$)
(x{~1~}, x{~3~}, x{~5~})=( $2$, $4$, $2$)
(x{~1~}, x{~4~}, x{~5~})=( $2$, $2$, $2$)
...
== include(page="template/taskfooter" task_id="maxpal") ==
