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

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


Timp maxim de executie/test:
0.1 secunde
Memorie totala disponibila/stiva:
16 MB/1 MB

Un sir de caractere se numeste ambigrama daca el arata identic când rotim foaia de hârtie pe care este scris cuvântul cu 180 de grade în jurul unei axe perpendiculare pe suprafata foii. Dându-se un cuvânt dorim sa îl transformam într-o ambigrama, prin modificarea sau stergerea unor litere din sir.

Cuvântul dat este scris cu litere mari ale alfabetului englez. Se observa ca:

  • literele H, I, N, O, S, X si Z arata nemodificate dupa rotatie;
  • literele M si W se transforma una în cealalta dupa rotatie.

Câteva exemple de ambigrame sunt: MOW, XXXXXXXX, XMIWX, HXHXHXH.

Dorim sa realizam modificari cât mai mici asupra sirului dat pentru a produce o ambigrama. Modificarile permise sunt:

  • inlocuirea unei litere cu o alta litera, operatie care are costul egal cu diferenta (in modul) dintre pozitiile in alfabet ale celor doua litere. De exemplu costul inlocuirii literei F cu litera H este 2 (F este litera a 6-a din alfabet iar H este cea de a 8-a litera in alfabet => cost=8-6=2); costul inlocuirii literei I cu litera F este 3=9-6;
  • stergerea unui caracter din sirul dat, costul in acest caz fiind egal cu distanta cea mai mica dintre litera care este stearsa si un caracter din afara alfabetului. Cu alte cuvinte stergerea caracterului ch din sirul dat are costul egal cu 1+min{dist(ch,'A'),dist(ch,'Z')}. De exemplu stergerea caracterului C are costul 3 (=1+min(2,23)) iar stergerea caracterului T are costul 7 (1+min(19,6)).

Cerinta

Se cere sa se scrie un program care determina pentru un cuvânt dat, ambigrama obtinuta cu cost minim prin operatiile descrise mai sus. Daca exista mai multe ambigrame de acelasi cost minim se va determina cea de lungime maxima. Daca si asa se obtin mai multe solutii se va determina pe cea mai mica în ordine alfabetica (lexicografica). Un sir vid nu este o ambigrama.

Date de intrare

Pe prima linie a fisierului de intrare ambigram.in se gaseste sir de caractere pentru care trebuie determinata ambigrama.

Date de iesire

Prima linie a fisierului de iesire ambigram.out va contine un numar natural reprezentând costul minim pentru a transforma cuvântul dat într-o ambigrama, iar a doua linie a fisierului de iesire va contine un sir de caractere reprezentând ambigrama obtinuta din sirul dat.

Restrictii

  • Cuvântul dat va contine între 1 si 150 de litere mari ale alfabetului englez.

Exemplu

ambigram.in ambigram.out Explicatii
BXAJ

7
WM

  • se sterge B cu cost 2
  • se înlocuieste X cu W cu cost 1
  • se sterge A cu cost 1
  • se înlocuieste J cu M cu cost 3

Observatie: Cu acelasi cost se obtine si ambigrama I (se sterg B, X si A si se înlocuieste J cu I) dar lungimea acestui sir este mai mica.

prof. Carmen Popescu
Colegiul National "Gheorghe Lazar" Sibiu
carmen_cngl@yahoo.com

propunător: Prof. Emanuela Cerchez
emanuela.cerchez@gmail.com
Probleme recomandate
De la .campion 2005: cuc, prime, radio, text2, honest, police, comori, patrate3, fisc, ref, pcod, zmeu, loc, nr01, scor2, judete, strict, convert, bile3, cod2, depou, auto2, tree, cat, nr3, chimie2, compress, jobs, leaves, zid, politics, onu2, ploaia, grazing, pstring, cartonase2, exp, cartoane, sir3, program, scoici, playlist, sqr, cai1, farfurii, joc1, trafic, carte, set, barbie, labirint, firma1, vile, game, donald, dans, albinuta, rlcs, stea, submatrix, cub1, ham, sponsori, young, jokes, pizza1, albine, lot, atac1, monede1, count, exam, herbert, sudoku, bio, metro
De acelaşi autor: light, sort, iepuras, pahare, turist, arthur, pento, cod2, game, jokes, trecere, paianjen, zumzi, cifru3, pamant, pixy, triburi, culori1, cifre5, arc
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, 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, palindrom1, minerale, speed, zmax, spider, cntgcd, interclasare, bus, pariuri, riglef, fractii2, fall, arbsum, conuri, arbvalmax, procente, metrou
surse trimise | ajutor