Runda 22 - Talia Kart

08.03.2010 - Przemysław Uznański
TrudnośćTrudność

 

Zawody stałe, runda 22

Limit czasowy: 5s, limit pamięciowy: 32MB;

 


Talia kart

Wyobraźcie sobie następującą sytuację, przyjaciele. Posiadacie talię złożoną z różnych kart (znacie kolejność kart w niej będących). Chcecie wykonać pewną imponującą kunsztem sztuczkę karcianą, ale aby to uczynić potrzebujecie ustawić kolejność kart w talii (nie zaszkodzi dopomóc szczęściu). Niestety, jedyna operacja jaką możecie wykonywać, to wyciągać kartę z talii i kłaść ją na koniec talii. Czy nie byłoby wspaniale wiedzieć, ile minimalnie ruchów potrzeba by ustawić żądaną kolejność kart w talii?

Wejście

Pierwsza liczba, to $ 1 \leq t \leq 100 $, liczba przypadków testowych. Kolejne $ t $ testów jest następującej postaci: Najpierw, $ 1 \leq n \leq 50000 $, rozmiar talii. Kolejna linia zawiera $ n $ różnych liczb ze zbioru $ \left\{1,2,..,n\right\} $ - to startowe ustawienie. Kolejna linia zawiera $ n $ różnych liczb ze zbioru $ \left\{1,2,..,n\right\} $ - to docelowe ustawienie.

Wyjście

Dla każdego przypadku testowego - dokładnie jedna liczba, najmniejsza potrzebna liczba ruchów, albo -1 gdy nie da się tak ustawić kart z takim startowym ustawieniem.

Przykład

Wejście:

1 6 4 2 3 1 5 6 4 3 1 5 6 2
Wyjście:
1
Nie możesz wysyłać i oglądać rozwiązań tego zadania ponieważ nie jesteś zalogowany. Zaloguj się lub załóż konto.
Warning: invalid codevent-ranking type.
PozycjaImię i nazwiskoWynikCzas
1Anna Piekarska1012:20:40
2Arek Wróbel1012:33:07
3Mateusz Wasilewski1031:34:57
4Przemysław Derengowski1031:42:34
5Krzysztof Drab1037:07:10
6Krzysztof Kulig1039:45:04
7Tomasz Wiatrowski10122:01:20
8Michal Zgliczynski10131:04:56
9Bartek Dudek10137:07:18
3.6
Twoja ocena: Brak Ocena: 3.6 (5 ocen)

Copyright © 2008-2010 Wrocławski Portal Informatyczny

design: rafalpolito.com