| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 | 128 MB | 2 | 0 | 0 | 0.000% |
Dane są dwa słowa u i v złożone z liter a i b. Naszym celem jest przekształcić słowo u w słowo v. 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ć u w v?
Pierwszy wiersz wejścia zawiera jedną liczbę całkowitą n (2 ≤ n ≤ 1 000 000), oznaczającą długość słów. Każdy z dwóch następnych wierszy zawiera ciąg złożony z n znaków a i/lub b. Pierwszy wiersz opisuje słowo u, a drugi - słowo v. 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 u można przekształcić w słowo v, wykonując jedynie operacje zamiany.
Jeśli odpowiedź jest twierdząca oraz n ≤ 4 000, 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ą m (1 ≤ m ≤ 1 000 000), oznaczającą liczbę operacji. Każdy z kolejnych m wierszy powinien zawierać dwie liczby całkowite ai, bi (1 ≤ ai, bi ≤ n - 1), oznaczające pozycje pierwszych liter zamienianych fragmentów ab (odpowiednio ai) i ba (odpowiednio bi).
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 m.
6 aabbaa baaaab
TAK 2 2 4 1 5
6 aaabbb ababab
NIE
Contest > Algorithmic Engagements > PA 2012 7-8번