Lista de probleme 2

Maria are în camera sa N mărgele așezate una lângă alta. Pe fiecare dintre ele este scris un număr natural format din cifre nenule distincte. Pentru fiecare mărgea, Maria șterge numărul și în locul său scrie altul, având doar două cifre, respectiv cifra minimă și cifra maximă din numărul scris inițial, în ordinea în care aceste cifre apăreau înainte de ștergere. Acum Maria consideră că mărgelele sunt de două tipuri, în funcție de numărul de două cifre scris pe ele: tipul 1 (cele care au cifra zecilor mai mică decât cifra unităților) și tipul 2 (celelalte). Folosind mărgelele, fetița dorește ca prin eliminarea unora dintre ele (dar fără să le schimbe ordinea celorlalte) să obțină un colier circular cât mai lung care să respecte proprietatea că oricare două mărgele vecine ale sale sunt de tipuri diferite. În colierul format cu mărgelele rămase după eliminare se consideră că prima mărgea este vecină cu ultima.

1) determinați numărul de mărgele de tipul 1;
2) determinați numărul maxim de mărgele pe care le poate avea colierul;

Un număr se numește palindrom dacă prima lui cifră este egală cu ultima, a doua cu penultima și așa mai departe. De exemplu numerele 1221, 505 și 7 sunt palindromuri, în vreme ce 500, 1410 și 2424 nu sunt palindromuri.

Similar, un număr se numește aproape palindrom dacă are aceleași perechi de cifre identice ca un palindrom, mai puțin o pereche în care cifrele diferă. De exemplu numerele 500, 1411, 2444, 1220, 53625, 14 și 4014 sunt numere aproape palindromuri, în vreme ce 1221, 1410, 6, 505, 22 și 512125 nu sunt numere aproape palindromuri deoarece fie sunt palindromuri, fie au prea multe perechi de cifre diferite.

Mai definim palindromul asociat al unui număr x ca fiind cel mai mic număr palindrom p strict mai mare decât x (p>x). De exemplu palindromul asociat al lui 5442 este 5445, palindromul asociat al lui 2445 este 2552, al lui 545 este 555, al lui 39995 este 40004, al lui 500 este 505, iar al lui 512125 este 512215.

Scrieţi un program care citind un număr natural nenul n și apoi un șir de n numere naturale determină:

1. câte dintre cele n numere sunt palindrom
2. câte dintre cele n numere sunt aproape palindrom
3. palindromurile asociate pentru cele n numere citite.