palindrom

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 (cu perechea de cifre neidentice îngroșată), î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$.

Cerință

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.

Date de intrare

Fișierul de intrare palindrom.in conține pe prima linie un număr $C$. Pentru toate testele, $C$ poate lua numai valorile $1$, $2$ sau $3$. Pe a doua linie se află numărul $n$, iar pe a treia linie cele $n$ numere naturale despărțite prin câte un spațiu.

Date de ieșire

Fișierul de ieșire palindrom.out:

• dacă $C = 1$, va conține un singur număr natural reprezentând numărul de numere palindrom din șir;
• dacă $C = 2$, va conține numărul de numere din șir care sunt aproape palindrom;
• dacă $C = 3$, va conține numerele palindrom asociate celor $n$ numere din șir, separate prin câte un spațiu.

Restricții și precizări

• $1 \leq n \leq 10 \ 000$;
• $1 \leq$ numerele din șir $\leq 2 \cdot 10^9$;
• Pentru rezolvarea corectă a primei cerințe se acordă $20$ de puncte.
• Pentru rezolvarea corectă a celei de a doua cerințe se acordă $30$ de puncte.
• Pentru rezolvarea corectă a celei de a treia cerințe se acordă $50$ de puncte.

Exemplul 1

palindrom.in

1
7
1221 500 53635 505 7 4004 1410

palindrom.out

5

Explicație

Explicație: Cele $5$ numere palindrom sunt $1221$, $53635$, $505$, $7$ și $4004$ ($C$ fiind $1$, se rezolvă doar prima cerință)

Exemplul 2

palindrom.in

2
4
5442 2445 545 39995

palindrom.out

3

Explicație

Explicație: Cele $3$ numere aproape palindrom sunt $5442$, $2445$ și $39995$ ($C$ fiind $2$, se rezolvă doar a doua cerință)

Exemplul 3

palindrom.in

3
11
6 1411 2444 1221 505 1220 53625 14 4014 1410 22

palindrom.out

7 1441 2552 1331 515 1221 53635 22 4114 1441 33

Explicație

Explicație: Palindromul asociat lui $6$ este $7$, al lui $1411$ este $1441$, al lui $2444$ este $2552$ etc. ($C$ fiind $3$, se rezolvă doar a treia cerință)