Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

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łowego50000B
Limit pamięci:1536MB
Cluster: Cube (Intel G860)
Języki programowania:All except: ASM64 GOSU JS-MONKEY

ukryj komentarze
2015-07-04 15:28:05 Marcin Kasprowicz
Racja, poprawiam definicję
2015-07-04 15:25:23 Jaroslaw Konczak
Męcząc się z jakimś dziwny WA znalazłem błąd logiczny w zadaniu.
W treści jest podane, że "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." natomiast widać w ostatnim przykładzie, że porządek liter nie musi zostać zmieniony, bo inaczej nie dało by się zamienić wyrazu abcd na anagram wyrazu abcf za pomocą tylko jednej operacji.

Ostatnio edytowany: 2015-07-04 15:26:12
2015-07-04 13:47:10 Marcin Kasprowicz
Od pierwszego słowa
2015-07-04 13:17:55 Dominik B.
Linie wejścia zaczynają się od pierwszego słowa, czy też mogą mieć najpierw białe znaki?
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.