palindrom

Algoritmul, pas cu pas

Cele trei cerințe sunt complet independente — valoarea lui $C$ îți spune ce să numeri. Ținem fiecare număr ca șir de cifre (un text), ca să putem compara ușor cifra de pe poziția din stânga cu cea din dreapta.

Cerința 1 — e deja palindrom?

Compari prima cifră cu ultima, a doua cu penultima, și așa mai departe spre mijloc. Dacă toate perechile coincid, numărul e palindrom.

• $12321$: $1=1$, $2=2$, mijlocul $3$ — palindrom.
• $10331$: prima pereche $1=1$, dar a doua $0 \ne 3$ — nu e palindrom.

Cerințele 2 și 3 — câte inserări îmi trebuie?

Ideea-cheie: pornesc cu doi indici, unul în stânga ($S$) și unul în dreapta ($D$), și îi apropii de mijloc.

1. Dacă cifrele de la cei doi indici coincid, perechea e bună: mut $S$ la dreapta și $D$ la stânga.
2. Dacă diferă, sunt obligat să inserez o cifră ca să creez perechea lipsă. Am exact două variante:
   • pun în stânga o copie a cifrei de la $D$ (atunci $D$ se mută spre stânga);
   • pun în dreapta o copie a cifrei de la $S$ (atunci $S$ se mută spre dreapta). Fiecare inserare costă $1$ din buget.
3. Singura piedică: nu pot pune cifra $0$ chiar la începutul numărului. Deci varianta „inserez în stânga" este interzisă când indicele $S$ este încă la poziția $0$ și cifra de copiat ar fi $0$.