Lista de probleme 2

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. Un număr care nu este palindrom poate fi transformat în palindrom adăugând la dreapta sa una sau mai multe cifre. 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.

Pentru un număr natural a definim costul ca fiind valoarea absolută (modulul) diferenței dintre a și numărul prim cel mai apropiat de a. Asupra unui șir de n numere naturale, situate pe poziții numerotate de la 1 la n, se aplică, în ordine, o succesiune de q operații. O operație constă dintr-o înlocuire și o afișare și este descrisă sub forma i x p, cu semnificația:

• mai întâi înlocuim cu x elementul din șir de pe poziția i;
• apoi afișăm suma minimă totală a costurilor unor elemente convenabil selectate de pe p poziții distincte din șir.

Cunoscând n și cele n elemente ale șirului, scrieți un program care să determine:
1. suma costurilor tuturor elementelor din șirul dat;
2. rezultatele afișate în urma aplicării fiecăreia dintre cele q operații, date în forma precizată.