In the event of technical difficulties with Szkopuł, please contact us via email at [email protected].
If you are familiar with IRC chat, the support team is also reachable on PIRC network (irc.pirc.pl
) in #szkopul
channel. If you are not, just use email.
Please do not ask us things like "how to solve task XYZ?".
Please remember that the support team has to sleep sometimes or go to work in real life.
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
?
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.
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 .
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.