Rezolvare PBinfo #4398

Un număr se numește palindrom dacă citit de la stânga la dreapta este identic cu numărul citit de la dreapta la stânga. De exemplu, numerele 131 și 15677651 sunt palindromuri. Un număr care nu este palindrom poate fi transformat în palindrom adăugând la dreapta sa una sau mai multe cifre.

Cerința

Dat fiind un șir de n numere naturale, scrieți un program care să rezolve următoarele două cerințe:
1. să se determine numărul minim total de cifre care trebuie să fie adăugate, astfel încât fiecare valoare din șir să fie palindrom;
2. considerând că putem adăuga cel mult S cifre, să se determine numărul maxim de termeni palindrom aflați pe poziții consecutive în șirul obținut.

Date de intrare

Fișierul de intrare palindrom.in conține pe prima linie numărul C, reprezentând cerința care trebuie să fie rezolvată (1 sau 2). Pe cea de a doua linie se află un număr natural n, reprezentând numărul de valori din șir. Pe următoarele n linii se află cele n numere din șir, câte un număr pe o linie. Dacă C = 2, pe ultima linie a fișierului de intrare se va afla numărul natural S reprezentând numărul maxim de cifre ce pot fi adăugate.

Date de ieșire

Fișierul de ieșire palindrom.out va conține o singură linie pe care va fi scris răspunsul la cerința C din fișierul de intrare.

Restricții și precizări

• 1 ≤ n ≤ 50.000; 0 ≤ S ≤ 500.000
• Numerele din șir au cel mult 50 de cifre.
• Pentru 15 puncte, C = 1 și n = 1
• Pentru 10 puncte, C = 2, S = 0, 1 < n ≤ 100 și numerele din șir au cel mult 18 cifre.
• Pentru 14 puncte, C = 1, 1 < n ≤ 1000 și numerele din șir au cel mult 18 cifre.
• Pentru 15 puncte, C = 2, S > 0, 1 < n ≤ 1000 și numerele din șir au cel mult 18 cifre.
• Pentru 16 puncte, C = 2, 1000 < n ≤ 50.000 și numerele din șir au cel mult 18 cifre.
• Pentru 13 puncte, C = 1, 1000 < n ≤ 50.000 și numerele din șir au între 19 și 50 de cifre.
• Pentru 17 puncte, C = 2, 1000 < n ≤ 50.000 și numerele din șir au între 19 și 50 de cifre.

Exemplul 1:

palindrom.in

1
5
12232
131
12345
0
7717

palindrom.out

7

Explicație

C = 1, n = 5. Pentru a transforma 12232 în palindrom trebuie să adăugăm minimum două cifre (1223221), pentru 12345 trebuie să adăugăm minimum 4 cifre (123454321), pentru 7717 trebuie să adăugăm minimum o cifră (77177), iar numerele 131 și 0 sunt deja palindromuri. În total 2 + 4 + 1 = 7.

Exemplul 2:

palindrom.in

2
7
12232
131
12345
0
7717
1244
215809
4

palindrom.out

3

Explicație

C = 2, n = 7, S = 4, deci se pot adăuga maximum 4 cifre. Putem adăuga cele 4 cifre numărului 12345 și obținem o secvență de lungime 3 formată numai din palindromuri (131 123454321 0). O altă variantă este de a adăuga o cifră la 7717 și două cifre la 21244 și obținem tot o secvență de lungime 3 formată numai din palindromuri (0 77177 124421). Pentru orice altă variantă, secvența de palindromuri obținută are mai puțini termeni.