Fișierul intrare/ieșire	palindrom3.in, palindrom3.out	Sursă	OJI 2023, clasa a 7-a
Autor	Emanuela Cherchez	Adăugată de	Mihai Tutu • mihai.tutu
Timp de execuție pe test	0.3 sec	Limită de memorie	65536 KB
Scorul tău	N/A	Dificultate	3

Vezi soluțiile trimise | Statistici

Palindrom3 (clasa a 7-a)

Un număr se numește palindrom dacă citit de la stânga la dreaptă este identic cu numărul citit de la dreaptă 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ță

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 palindrom3.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 palindrom3.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

• 1 ≤ n ≤ 50 000
• 0 ≤ S ≤ 500 000
• Numerele din șir au cel mult 50 de cifre.

#	Punctaj	Restricții
1	15	C = 1 și n = 1.
2	10	C = 2, S = 0, 1 < n ≤ 100 și numerele din șir au cel mult 18 cifre.
3	14	C = 1, 1 < n ≤ 1000 și numerele din șir au cel mult 18 cifre.
4	15	C = 2, S > 0, 1 < n ≤ 1000 și numerele din șir au cel mult 18 cifre.
5	16	C = 2, 1000 < n ≤ 50 000 și numerele din șir au cel mult 18 cifre.
6	13	C = 1, 1000 < n ≤ 50 000 și numerele din șir au între 19 și 50 de cifre.
7	17	C = 2, 1000 < n ≤ 50 000 și numerele din șir au între 19 și 50 de cifre.

Exemple

castel.in	castel.out	Explicații
1 5 12232 131 12345 0 7717	7	C = 1, n = 5. Pentru a transforma 12232 în palindrom trebuie să adăugăm minimum 2 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.
2 7 12232 131 12345 0 7717 1244 215809	3	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 1244 ș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.