Transformacje
Limit pamięci: 128 MB
Dane są dwa słowa i złożone z liter a i b.
Naszym celem jest przekształcić słowo w słowo .
Mamy w tym celu do dyspozycji następującą operację zamiany:
wybieramy dwa rozłączne fragmenty ab i ba
w pierwszym słowie i zamieniamy je miejscami.
Czy, wykonując skończoną liczbę takich operacji, możemy przekształcić w ?
Wejście
Pierwszy wiersz wejścia zawiera jedną liczbę całkowitą
(), oznaczającą długość słów.
Każdy z dwóch następnych wierszy zawiera ciąg złożony z znaków a
i/lub b.
Pierwszy wiersz opisuje słowo , a drugi - słowo .
Możesz założyć, że słowa te będą różne.
Wyjście
W pierwszym wierszu wyjścia powinno znaleźć się jedno słowo TAK
lub NIE, oznaczające, czy słowo można przekształcić
w słowo , wykonując jedynie operacje zamiany.
Jeśli odpowiedź jest twierdząca oraz ,
Twój program powinien także wypisać przykładowy ciąg operacji
prowadzących do celu.
Pierwszy wiersz tego opisu powinien zawierać jedną liczbę całkowitą
(), oznaczającą liczbę operacji.
Każdy z kolejnych wierszy powinien zawierać dwie liczby całkowite
, (), oznaczające pozycje
pierwszych liter zamienianych fragmentów ab (odpowiednio )
i ba (odpowiednio ).
Jeśli istnieje wiele możliwych rozwiązań, Twój program powinien wypisać
jakiekolwiek z nich.
W szczególności Twoje rozwiązanie nie musi minimalizować liczby operacji,
tj. liczby .
Przykład
Dla danych wejściowych:
6
aabbaa
baaaab
poprawną odpowiedzią jest:
TAK
2
2 4
1 5
natomiast dla danych:
6
aaabbb
ababab
poprawną odpowiedzią jest:
NIE
Autor zadania: Adam Polak.