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
Wcu
cost 1
se sterge Acu cost 1
se înlocuieste
J cu
Mcu
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.