ambigram

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

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

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.

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

ambigram.in	ambigram.out	Explicatii
BXAJ	25 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.