- Language:
- Time limit: 1.00 s
- Memory limit: 512 MB
Merkkijonon jokainen merkki on 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.