- Language:
- Time limit: 1.00 s
- Memory limit: 512 MB
A
tai B
. Voit muuttaa merkkijonoa tekemällä siirtoja, joissa vaihdetaan kaksi merkkiä keskenään.Tehtäväsi on järjestää merkit niin, että ensin tulevat kaikki
A
-merkit ja sitten kaikki B
-merkit. Montako siirtoa tarvitset vähintään?Esimerkiksi kun merkkijono on
BBAAB
, siirtoja tarvitaan vähintään $2$. Yksi ratkaisu on BBAAB
$\rightarrow$ ABBAB
$\rightarrow$ AABBB
.Syöte
Ensimmäisellä rivillä on kokonaisluku $t$: merkkijonojen määrä.
Kullakin seuraavalla rivillä on merkkijono, jonka jokainen merkki on
A
tai B
.Tuloste
Tulosta kunkin merkkijonon pienin siirtojen määrä omalle rivilleen.
Esimerkki
Syöte:
5
AABA
AAABBB
BB
BBAAB
BAABABBBBBABABB
Tuloste:
1
0
0
2
2
Arvostelu
Koodiasi testataan syötteellä, jossa $t=1000$ ja kunkin merkkijonon pituus on enintään $100$. Saat tehtävästä $100$ pistettä, jos koodisi antaa oikean vastauksen kaikille merkkijonoille.