== include(page="template/taskheader" task_id="maxpal") ==
Poveste şi cerinţă...
Ş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ă.
h2. Date de intrare
Fişierul de intrare $maxpal.in$ ...
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.
h2. Date de ieşire
În fişierul de ieşire $maxpal.out$ ...
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$**.
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 |
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
| 5
2 1 4 2 2
| 3 5
|
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") ==
