.campion
conectare | înregistrare | căutare
Pagina principală » Probleme » palindrom1

ultima problemă
grupă: mică
sursă: OMI 2016
ultimul articol
autor: Prof. Radu Vişinescu
ultimul software
autor: Prof. Emanuela Cerchez
palindrom1


Timp maxim de execuţie / test:
0.6s
Memorie totala disponibilă / stivă:
256MB / 64MB

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 palindrom1.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 palindrom1.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.

Exemple

palindrom1.inpalindrom1.outExplicaţii
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.

autor: Robert Hasna
propunător: Prof. Emanuela Cerchez
Colegiul Naţional ″Emil Racoviţă″
emanuela.cerchez@gmail.com
Probleme recomandate
De la ONI 2012: culegere, culori2, stele1, cartier, medalion, numar5, bile6, proiecte, zigzag, alune, cuburi4, optim, cifreco, patru, puncte5, unuzero, sstabil, intersectii, copaci2, 7segmente, amedie, cutie1, drept2, gheizere, plus, poly, minerale
De acelaşi autor: furnici1
Despre programare dinamică: vedete, fbr, tgv, zeratul, rv, comun, retea, circuit, sumdif, copaci, drum, text, palind, joc, vikingi, rafturi, balaur, plimbare, party, pc, pioni, seif, iepuri, numere3, perm, ture, bilete, prop, ro, reduceri, cuburi, invest, cutie2, stalpi, nr2, judete, strict, auto2, tree, jobs, leaves, pstring, program, datorii, senzori, farfurii, joc1, barbie, ambigram, rlcs, cub1, bio, chimie1, otilia, pasune, remi, sir23, tren1, joc5, pachete, echipe, comb, agitatie, ivv, peste, pitici, pipe, shgraf, tabara1, stop, randuri, zidar, log, sant, produs, subsir, cover, bcast, emax, dist, mesaj1, imax, avere, asmax, raft, suma2, joc12, fni, nr4, join, transport, masina3, lsort, microvirus, fat, cafea, echipe1, anticip, bsir, diamant, petrom, evantai, spion, acolor, evo, bombo, lacusta, lant, team, pitici1, numere8, dep, stiva, subgeom, pviz, tir1, cabane, piramida1, mosia, cuvinte1, gaina, materom, sortari, turnuri, trans, politie, codul, dansatori, nkbiti, kperms, treegame, siruri2, 123, jucarii, bradut, joc15, expozitie, text3, ic, echilibru, distsir, kmax, stalpi1, gaz, triunghi2, v2d, cuiburi, mine, orientare, activ, secvbiti, kcons, pokemon, ubergraf, left, acerc, autostrazi, kdist, select, cazare, fluviu, telecomanda, parcela, pion, subs, suma4, sirmax, bdotcom, viena, sablon2, telecab, ikebana, radare, hacker, obstacole, robotel, centrala, verigi, cds, wg, minusk, radioactiv, enigma, jb, efect, maxviz, ripstick, progresii, maxtri, combcuv, blis, subsiruri, mijloc, probleme, unuzero, minerale, speed, zmax, spider, cntgcd, interclasare, bus, pariuri, riglef, fractii2, fall, arbsum, conuri, arbvalmax, procente, metrou
surse trimise | ajutor