| Fişierul intrare/ieşire: | palindrom3.in, palindrom3.out | Sursă | ONI 2012 - clasa a 9-a |
| Autor | Alexandru Cazacu, Cosmin-Mihai Tutunaru, Dragos Oprica, Robert Hasna, Vlad Duta, Vlad Ionescu | Adăugată de |  Simoiu Robert •SpiderMan |
| Timp execuţie pe test | 0.2 sec | Limită de memorie | 128000 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
Palindrom3
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 
cifrelor unui număr, utilizând un tablou de corespondenţe T.
O cifră c a unui număr poate fi înlocuită cu cifra corespunzătoare ei, Tc.
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 ?
Cerinţă
Cunoscând valorile T0, T1, …, T9, 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.
Date de intrare
Pe prima linie a fişierului palindrom3.in sunt memorate 10 cifre distincte, separate prin câte un spaţiu, reprezentând valorile T0, T1, …, T9.
Pe a doua linie sunt memorate cifrele numărului N, iar pe cea de a treia linie un numărul natural K.
Date de ieşire
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.
Restricţii
- 1 ≤ N < 101 000 000;
- N are un număr par de cifre;
- 2 ≤ K ≤ 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.
Exemplu
| palindrom3.in | palindrom3.out | Explicaţie |
|---|---|---|
| 0 4 6 5 1 2 7 8 9 3 1234 3 | 4994 4224 | 1234 → 4234 → 4634 → 4734 → 4834 → 4934 → 4954 → 4924 → 4964 → 4974 → 4984 → 4994 Numărul N trece prin următoarele stări înainte de a deveni palindrom cu valoarea maximă, divizibil cu 3: 1234 → 4234 → 4254 → 4224. |
