NézetNyomtat

Apokaliptikus sorrend (Megoldás)
Címkék > Feladat

Apokaliptikus sorrend

Stanford Local Programming Contest, 2008. 1. feladat
Az alma és a banán finom, de veszélyes is! Egy ősi profécia szerint a világ megsemmisül, ha almákat és banánokat megfelelő sorrendben teszünk le egymás mellé. Egy ködös, szürke reggelen elhatározod, hogy kipróbálod, működik-e a dolog. Adott almák és banánok egy sorozata, és egy megengedett lépést szabad ismételgetni: tetszőleges számú szomszédos gyümölcs lecserélhető egyféle (vagy csak alma, vagy csak banán) gyümölcsre. Alig várod, hogy elpusztuljon a világ, ezért a lehető legkevesebb lépésben szeretnél eljutni az apokaliptikus sorrendhez.

Feladat

Írj programot, ami kiszámítja, hogy legkevesebb hány lépés kell a pusztítás végrehajtásához!

Bemenet

A bemenet első sora a fájlban található tesztesetek $t\, (t \le 100)$ számát adja meg. Minden teszteset két egymás utánio sorban található, az első az eredeti sorrendet, a második pedig az ördögi sorrendet tartalmazza. Mindkét sor csak 'A' és 'B' karaktereket tartalmaz, legfeljebb 200-at és a két sor hossza azonos. A karakterek előtt és mögött nincsenek szóközök.

Kimenet

Minden tesztesethez írjuk ki (külön sorba), hogy legkevesebb hány lépés kell a világ elpusztításához!

Példa

alignment.inalignment.out
2
BB
AA
BAAAB
ABBAA
1
2

Tesztadatok