== include(page="template/taskheader" task_id="palindrom3") ==

Poveste şi cerinţă...

p<>. Cu mult timp în urmă, într-un tărâm foarte, foarte îndepărtat, a existat o ţară numită Tnamap. Locuitorii acestei ţări puteau să aplice instantaneu transformări asupra {!>problema/palindrom3?x.jpg!} cifrelor unui număr, utilizând un tablou de corespondenţe $T$.
 
p<>. O cifră $c$ a unui număr poate fi înlocuită cu cifra corespunzătoare ei, $T$~$c$~.
 
p<>. $Dalv$ şi $Sogard$, doi indivizi speciali ai acestei societăţi ciudate se aflau în drum spre $INO$ când au conştientizat că pot transforma instantaneu, folosind număr minim de transformări de cifre, orice număr $N$ într-un palindrom divizibil cu un număr natural $K$. Dacă sunt mai multe astfel de numere, îl determină pe cel mai mare.
Voi puteţi ?
 
h2. Cerinţă
 
Cunoscând valorile $T$~$0$~, $T$~$1$~, …, $T$~$9$~, numărul ce urmează a fi transformat $N$ şi numărul $K$ (divizorul palindromului), determinaţi:
 
# Numărul maxim care se poate obţine aplicând transformări succesive numărului $N$ dat.
# Cel mai mare dintre palindromurile divizibile cu $K$, ce se pot obţine din numărul $N$, efectuând un număr minim de transformări asupra cifrelor numărului dat, respectiv asupra cifrelor numerelor obţinute pe parcurs.

h2. Date de intrare

Fişierul de intrare $palindrom3.in$ ...

p<>. Pe prima linie a fişierului $palindrom3.in$ sunt memorate $10$ cifre distincte, separate prin câte un spaţiu, reprezentând valorile $T$~$0$~, $T$~$1$~, …, $T$~$9$~.
Pe a doua linie sunt memorate cifrele numărului $N$, iar pe cea de a treia linie un numărul natural $K$.

h2. Date de ieşire

În fişierul de ieşire $palindrom3.out$ ...

p<>. Fişierul $palindrom3.out$ va conţine pe prima linie numărul maxim care se poate obţine aplicând transformări succesive numărului $N$, iar pe a doua linie palindromul divizibil cu $K$,de valoare maximă, ce se poate obţine din numărul $N$, efectuând un număr minim de transformări asupra cifrelor.

h2. Restricţii

* $... ≤ ... ≤ ...$

* $1 &le; N < 10^1 000 000^$;
* $N$ are un număr par de cifre;
* $2 &le; K &le; 20$;
* se garantează faptul că toate testele au soluţie;
* pentru rezolvarea primei cerinţe se va acorda $20%$ din punctaj, iar pentru rezolvarea celei de-a doua cerinţe se va acorda $80%$ din punctaj.

h2. Exemplu

table(example). |_. palindrom3.in |_. palindrom3.out |
| This is some
  text written on
  multiple lines.
| This is another
  text written on
  multiple lines.
|
 
h3. Explicaţie

table(example). |_. palindrom3.in |_. palindrom3.out |_. Explicaţie |
| 0 4 6 5 1 2 7 8 9 3
1234
3
| 4994
4224
| {*1*}234 → 4{*2*}34 → 4{*6*}34 → 4{*7*}34 → 4{*8*}34 → 4{*9*}34 → 49{*5*}4 → 49{*2*}4 → 49{*6*}4 → 49{*7*}4 → 49{*8*}4 → {*4994*}
Numărul N trece prin următoarele stări înainte de a deveni palindrom cu valoarea maximă, divizibil cu 3:
{*1*}234 → 42{*3*}4 → 42{*5*}4 → {*4224*}.
|

...

== include(page="template/taskfooter" task_id="palindrom3") ==

7733