Fişierul intrare/ieşire:palindrom3.in, palindrom3.outSursăONI 2012 - clasa a 9-a
AutorAlexandru Cazacu, Cosmin-Mihai Tutunaru, Dragos Oprica, Robert Hasna, Vlad Duta, Vlad IonescuAdăugată deSpiderManSimoiu Robert SpiderMan
Timp execuţie pe test0.2 secLimită de memorie128000 kbytes
Scorul tăuN/ADificultateN/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:

  1. Numărul maxim care se poate obţine aplicând transformări succesive numărului N dat.
  2. 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.inpalindrom3.outExplicaţ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.
Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content