Zgłaszanie | Wszystkie zgłoszenia | Najlepsze | Lista |
AL_23_02 - Czas na anagramy |
Jasio jest bardzo dobrze znanym Contest-setterem. Właśnie przygotowuje się do kolejnej MXXXI rudny Algoligi. Postanowił, że drugie zadanie będzie związane z anagramami. Zadanie polega na tym, że dla dwóch podanych słów, które są anagramami, należay permutować jeden anagram minimalną liczbę razy tak, aby otrzymać drugie słowo. Niestety, Jasio jeszcze nie umie tworzyć automatycznie testów, więc stworzył wszystkie ręcznie, a o sprawdzenie ich poprawności poprosił Stasia. Stasio przeanalizował testy i okazało się, że z powodu roztargnienia Jasia, wiele par nie jest anagramami. Postanowił napisać więc program, który w optymalny sposób zamieni podane dwa słowa w anagramy. Zrób to samo i dla zadanych dwóch słów określ ile minimalnie należy wykonać operacji, aby powstały anagramy. Jako operację rozumiemy:
- dodanie litery do słowa
- usunięcie litery ze słowa
- zamiana litery na inną
Anagram to wyraz lub zdanie powstałe po przestawieniu liter innego wyrazu (zdania). Oba wyrazy składają się z tych samych liter, tylko w innym porządku. W szczególnym przypadku oba wyrazy są tożsamościowe.
Kilka przykładów:
- adam dama
- algoliga golagali
Wejście
W pierwszym wierszu jedna liczba określająca liczbę zestawów danych (nie więcej niż tysiąc).
Każdy zestaw danych składa się z dwóch wyrazów zapisanych w tej samej linii złożonych wyłącznie z małych liter języka łacińskiego. Długość każdego z nich mieści się w przedziale: [1..1000 000].
Wyjście
Dla każdego zestawu jedna liczba określająca ilość wykonanych operacji.
Przykład
Wejście: 3 adam dama abc abcd abcd abcf
Wyjście: 0 1 1
Dodane przez: | Marcin Kasprowicz |
Data dodania: | 2015-06-03 |
Limit czasu wykonania programu: | 1s |
Limit długości kodu źródłowego | 50000B |
Limit pamięci: | 1536MB |
Cluster: | Cube (Intel G860) |
Języki programowania: | All except: ASM64 GOSU JS-MONKEY |