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.in | alignment.out |
|
2 BB AA BAAAB ABBAA |
1 2 |