302 - PalindromČasový limit: 6s, Pamäťový limit: 64MiBProgramovacie jazyky: Pascal, C, C++, Java, C++0x, Python 3Obtiažnosť:  Náročná[ Pošli riešenie ] [ Tvoje riešenia ] [ Správne riešenia ] [ Vzorové riešenie ] ÚlohaDaný je reťazec zložený z malých písmen anglickej abecedy ('a'-'z'). Zistite, koľko minimálne výmen susedných znakov potrebujeme, aby sme dostali palindróm (tj. slovo, ktoré je zhodné so svojím zrkadlovým obrazom), prípadne, že sa to nedá. Napríklad, reťazec "mamad" vieme pretransformovať na palindróm "madam" v 3 krokoch:
VstupVstup obsahuje na prvom riadku číslo t (1≤t≤10), počet vstupných slov. Každé vstupné slovo je napísané na samostatnom riadku, je neprázdne, skladá sa len z malých písmen 'a'-'z' a nie je dlhšie ako 50000 znakov.VýstupVýstup by mal obsahovať pre každé vstupné slovo jediný riadok, a na ňom buď jediné číslo, určujúce minimálny počet výmen, alebo slovo "Impossible" (bez úvodzoviek), ak sa dané slovo na palindróm premeniť nedá.PríkladVstup:3 mamad asflkj aabb Výstup:3 Impossible 2 Príklad pridal Marián Dvorský. Pôvodné zadanie zo súťaže Waterloo. |